Multiset Colorings of Random Graphs Across Density Regimes

Source abstract

We show that almost every graph admits a partition of its vertex set into three parts such that no two adjacent vertices have the same number of neighbors in each of the three parts. Equivalently, for $G\sim G(n,1/2)$, $χ_m(G)\le3$ with high probability, improving the previously known bound of five. Here $χ_m(G)$ denotes the multiset chromatic number of $G$, the minimum number of parts in a vertex partition whose neighbor-count vectors distinguish every pair of adjacent vertices. In fact, the three-part bound holds for every fixed $0.185<p<0.509$. More generally, for every fixed $p\in(0,1)$, $G\sim G(n,p)$ satisfies $χ_m(G)\le4$ with high probability. These results are obtained by converting the unresolved edges of a carefully chosen initial partition into hyperplanes of a Boolean cube and applying the Linial--Radhakrishnan theory of essential covers. We also determine how $χ_m(G)$ grows when the graph is polynomially close to complete. For every fixed $β\in(0,1)$ and $G\sim G\!\left(n,1-n^{-(1-β)}\right)$, with high probability $\frac{2}β\le χ_m(G)\le \left\lfloor\frac{2}β\right\rfloor+5$. Thus $χ_m(G)=2/β+O(1)$. The lower bound is spectral, while the upper bound follows from multinomial anti-concentration and the Lov'asz Local Lemma.