English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

An equitable colouring of a graph $G$ is a colouring of the vertices of $G$so that no two adjacent vertices are coloured the same and, additionally, thecolour class sizes differ by at most $1$. The equitable chromatic number$\chi_=(G)$ is the minimum number of colours required for this. We study theequitable chromatic number of the dense random graph $G(n,m)$, where $m =\left\lfloor p {n \choose 2} \right \rfloor $ and $0<p< 0.86$ is constant. Itis a well-known question of Bollob\'as whether for $p=1/2$ there is a function$f(n) \rightarrow \infty$ so that for any sequence of intervals of length$f(n)$, the normal chromatic number of $G(n,m)$ lies outside the intervals withprobability at least $1/2$ if $n$ is large enough. Bollob\'as proposes thatthis is likely to hold for $f(n) = \log n$. We show that for the\emph{equitable} chromatic number, the answer to the analogous question isnegative. In fact, there is a subsequence $(n_j)_{j}$ of the integers where$\chi_=(G(n_j,m_j)) = n/j$ with high probability, i.e., $\chi_=(G(n_j,m_j))$ isconcentrated on exactly one explicitly known value. This constitutessurprisingly narrow concentration since in this range the equitable chromaticnumber, like the normal chromatic number, is rather large in absolute value,namely asymptotically equal to $n / (2\log_b n)$ where $b=1/(1-p)$.

Sharp concentration of the equitable chromatic number of dense random graphs