Upper-bounding the k-colorability threshold by counting covers

Introduction

Let $G(n,m)$ be the random graph on $V=\left\{{1,\ldots,n}\right\}$ with $m$ edges. Unless specified otherwise, we let $m=\lceil dn/2\rceil$ for a number $d>0$ that remains fixed as $n\rightarrow\infty$. Let $k\geq 3$ be an $n$-independent integer. We say that $G(n,m)$ has a property ${\cal E}$ with high probability (‘w.h.p.’) if $\lim_{n\rightarrow\infty}\operatorname{P}\left[{G(n,m)\in{\cal E}}\right]=1$.

Here and throughout the paper, we use the symbol $o_{k}(1)$ to hide terms that tend to zero for large $k$. The bound (2) was recently improved , also via a second moment argument, for sufficiently large $k$ to

This leaves an additive gap of $2\ln 2+o_{k}(1)$ between the upper bound (1) and the lower bound (3).

The problem of $k$-coloring $G(n,m)$ is closely related to the “diluted mean-field $k$-spin Potts antiferromagnet” model of statistical physics. Indeed, over the past decade physicists have developed sophisticated, albeit mathematically non-rigorous formalisms for identifying phase transitions in random discrete structures, the “replica method” and the “cavity method” (see for details and references). Applied to the problem of $k$-coloring $G(n,m)$ , these techniques lead to the conjecture that

Theorem 1.1 improves the naive first moment bound (1) by about an additive $1$. This proves, perhaps surprisingly, that the $k$-colorability threshold (if it exists) does not coincide with the first moment bound. Furthermore, Theorem 1.1 narrows the gap to the lower bound (3) to $2\ln 2-1+o_{k}(1)\approx 0.39$.

into $N=\exp(\Omega(n))$ non-empty “clusters” ${\mathcal{C}}_{i}$ such that for any two colorings $\sigma,\tau$ that belong to distinct clusters we have

In other words, the clusters are well-separated. Furthermore, a “typical” cluster ${\mathcal{C}}_{i}$ is characterized by a set of $\Omega(n)$ “frozen” vertices, which have the same color in all colorings $\sigma\in{\mathcal{C}}_{i}$. Roughly speaking, a cover is a representation of a cluster ${\mathcal{C}}_{i}$: the cover details the colors of all the frozen vertices, while the non-frozen ones are represented by the “joker color” . We will define covers precisely in Section 3.

The key idea behind the proof of Theorem 1.1 is to apply the first moment method to the number of covers. Since, according to the cavity method, covers are in one-to-one correspondence with clusters, we carry effectively out a first moment argument for the number of clusters. The improvement over the “classical” first moment bound for the number of $k$-colorings results because this approach allows us to completely ignore the cluster sizes $|{\mathcal{C}}_{i}|$. Indeed, close to the $k$-colorability threshold the cluster sizes are conjectured to vary wildly, as has in part been established rigorously in . By contrast, the “classical” first moment argument amounts to putting a rather generous uniform bound on all the cluster sizes.

Assume that $d\geq 2k\ln k-\ln k-4+o_{k}(1)$. There is a number $\delta_{k}>0$ such that w.h.p. every $k$-coloring $\sigma$ of the random graph $G(n,m)$ has a set $F(\sigma)$ of $\delta_{k}$-frozen vertices of size $|F(\sigma)|\geq(1-o_{k}(1))n$.

Due to the (conjectured) relationship between freezing and the demise of local-search algorithms, it would be interesting to identify the precise threshold where all the $k$-colorings of $G(n,m)$ are frozen.

The key idea in this line of work is to estimate the first moment of the number of “rigid” colorings: for any two colors $1\leq i<j\leq k$, every vertex of color $i$ must have neighbors of color $j$ . Clearly, any $k$-colorable graph must have a rigid $k$-coloring. At the same time, the number of rigid $k$-colorings can be expected to be significantly smaller than the total number of $k$-colorings, and thus one might expect an improved first-moment upper bound. However, in terms of the clustering scenario put forward by physicists, it is conceivable that many clusters contain a large (in fact, exponentially large) number of rigid $k$-colorings. Therefore, the idea of counting rigid $k$-colorings seems conceptually weaker than the approach of counting clusters pursued in the present work. In fact, the improvement obtained by counting rigid colorings appears to diminish for larger $k$ .

A fairly new approach to obtaining upper bounds on thresholds in random constraint satisfaction problems is the use of the interpolation method . This technique gives an upper bound on, e.g., the $k$-colorability threshold in terms of a variational problem that is related to the statistical mechanics techniques. However, this variational problem appears to be difficult to solve. Thus, it is not clear (to me) how an explicit upper bound as stated in Theorem 1.1 can be obtained from the interpolation method.

Dani, Moore and Olson studied a variant of the graph coloring problem in which each pair of $(u,v)$ of vertices comes with a random permutation $\pi_{u,v}$ of the $k$ possible colors; this gives rise to a concept of “permuted” $k$-colorings. They obtained an upper bound of $2k\ln k-\ln k-1+o_{k}(1)$ on the threshold for the existence of permuted $k$-colorings. The proof is based on counting the total weight of $k$-colorings and using an isoperimetric inequality. Moreover, as pointed out in , physics intuition suggests that the threshold in the permuted $k$-coloring problem matches the “unpermuted” $k$-colorability threshold.

In the context of satisfiability, Maneva and Sinclair used the concept of covers to obtain a conditional upper bound on the random $3$-SAT threshold. Roughly speaking, the condition that they need is that w.h.p. all satisfying assignments have frozen variables. However, verifying this condition in random 3-SAT is an open problem. (That said, it is conceivable that the approach used in might yield a better upper bound on the $k$-SAT threshold for large $k$.)

Preliminaries

Let $\left[{k}\right]=\left\{{1,2,\ldots,k}\right\}$. Because Theorem 1.1 and Corollary 1.2 are asymptotic statements in both $k$ and $n$, we may generally assume that $k\geq k_{0}$ and $n\geq n_{0}$, where $k_{0},n_{0}$ are constants that are chosen sufficiently large for the various estimates to hold.

We perform asymptotic considerations with respect to both $k$ and $n$. When referring to asymptotics in $k$, we use the notation $O_{k}(\cdot)$, $o_{k}(\cdot)$, etc. Asymptotics with respect to $n$ are just denoted by $O(\cdot)$, $o(\cdot)$, etc.

If $G$ is a (multi-)graph and $A,B$ are sets of vertices, then we let $e_{G}(A,B)$ denote the number of $A$-$B$-edges in $G$. Moreover, $e_{G}(A)$ denotes the number of edges inside of $A$. If $A=\left\{{v}\right\}$ is a singleton, we just write $e_{G}(v,B)$. The reference to $G$ is omitted where it is clear from the context.

The random graph $G(n,m)$ consists of $m$ edges that are chosen almost independently. To simplify some of the arguments below, we are going to work with a random multi-graph model $G^{\prime}(n,m)$ in which edges are perfectly independent. More precisely, $G^{\prime}(n,m)$ is obtained as follows: let \mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}=(\mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{1},\ldots,\mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{m})\in(V\times V)^{m} be a uniformly random $m$-tuple of ordered pairs of vertices. In other words, each \mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{i} is chosen uniformly out of all $n^{2}$ possible vertex pairs, independently of all the others. Now, let $G^{\prime}(n,m)$ be the random multi-graph comprising of \mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{1},\ldots,\mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{m} viewed as undirected edges. Thus, $G^{\prime}(n,m)$ may have self-loops (if \mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{i}=(v,v) for some index $i$) as well as multiple edges (if, for example, \mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{i}=(u,v) and \mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{j}=(v,u) with $1\leq i<j\leq m$ and $u\neq v$). The two random graph models are related as follows.

For any event $\mathcal{A}$ we have $\operatorname{P}\left[{G(n,m)\in\mathcal{A}}\right]\leq O(1)\cdot\operatorname{P}\left[{G^{\prime}(n,m)\in\mathcal{A}}\right]$.

Proof. The random graph $G^{\prime}(n,m)$ has at most $m$ distinct edges, and no self-loops. Let ${\cal E}$ be the event that it has exactly $m$ edges. This is the case iff \mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{1},\ldots,\mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{m} induce pairwise distinct undirected edges. Given the event ${\cal E}$, $G^{\prime}(n,m)$ is identical to $G(n,m)$. Hence,

Thus, the assertion follows from (5). $\Box$

The Chernoff bound.

We need the following Chernoff bound on the tails of a binomially distributed random variable (e.g., [23, p. 21]).

Let $\varphi(x)=(1+x)\ln(1+x)-x$. Let $X$ be a binomial random variable with mean $\mu>0$. Then for any $t>0$ we have

Balls and bins.

Consider a balls and bins experiment where $\mu$ balls are thrown independently and uniformly at random into $\nu$ bins. Thus, the probability of each distribution of balls into bins equals $\nu^{-\mu}$. We will need the following well-known “Poissonization lemma” (e.g., [16, Section 2.6]).

In the above experiment let $e_{i}$ be the number of balls in bin $i\in\left[{\nu}\right]$. Moreover, let $\lambda>0$ and let $(b_{i})_{i\in\left[{\nu}\right]}$ be a family of independent Poisson variables, each with mean $\lambda$. Then for any sequence $(t_{i})_{i\in\left[{\nu}\right]}$ of non-negative integers such that $\sum_{i=1}^{\nu}t_{i}=\mu$ we have

Hence, the joint distribution of $(e_{i})_{i\in\left[{\nu}\right]}$ coincides with the joint distribution of $(b_{i})_{i\in\left[{\nu}\right]}$ given $\sum_{i=1}^{\nu}b_{i}=\mu$.

We are typically going to use Lemma 2.3 to obtain an upper bound on the probability on the left hand side. Therefore, the following simple corollary will come in handy.

With the notation of Lemma 2.3, assume that $\lambda=\mu/\nu>0$. Then for any sequence $(t_{i})_{i\in\left[{\nu}\right]}$ of non-negative integers such that $\sum_{i=1}^{\nu}t_{i}=\mu$ we have

Proof. Let $b=\sum_{i=1}^{\nu}b_{i}=\mu$. Since the $b_{i}$ are independent Poisson variables with means $\lambda=\mu/\nu$, $b$ is Poisson with mean $\mu$. By Stirling’s formula, $\operatorname{P}\left[{b=\mu}\right]=\mu^{\mu}\exp(-\mu)/\mu!=\Omega(\mu^{-1/2})$. Hence, Lemma 2.3 yields

Covers

Let $G=(V,E)$ be a graph, let $k\geq k_{0}$ be an integer, and let $\sigma:V\rightarrow\left[{k}\right]$ be a $k$-coloring of $G$. We would like to identify a set $F\subset V$ of vertices whose colors cannot be changed easily by a “local” recoloring of a few vertices. For instance, if $v$ is a vertex that does not have a neighbor of color $j$ for some $j\in\left[{k}\right]\setminus\left\{{\sigma(v)}\right\}$, then $v$ can be recolored easily. More generally, we would like to say that, recursively, a vertex can be recolored easily if there is a color $j$ such that all its neighbors of color $j$ can be easily recolored. To formalize this, we need the following concept.

Let $\zeta:V\rightarrow\left\{{0,1,\ldots,k}\right\}$. We call $v\in V$ stable under $\zeta$ if $\zeta(v)\neq 0$ and if for any color $j\in\left[{k}\right]\setminus\left\{{\zeta(v)}\right\}$ there are at least two neighbors $u_{1},u_{2}$ of $v$ such that $\zeta(u_{1})=\zeta(u_{2})=j$.

Now, consider the following whitening process that, given a $k$-coloring $\sigma$ of $G$, returns a map $\hat{\sigma}:V\rightarrow\left\{{0,1,\ldots,k}\right\}$; the idea is that $\hat{\sigma}(v)=0$ for all $v$ that are easy to recolor.

Initially, let $\hat{\sigma}(v)=\sigma(v)$ for all $v\in V$.

While there exist a vertex $v\in V$ with $\hat{\sigma}(v)\neq 0$ that is not stable under $\hat{\sigma}$, set $\hat{\sigma}(v)=0$.

The process WH1–WH2 is similar to processes studied in in the context of random graph coloring, and in in the context of random $k$-SAT. (The term “whitening process” stems from .) Clearly, the final outcome $\hat{\sigma}$ of the whitening process is independent of the order in which WH2 proceeds.

The intuition behind the whitening process is that if we attempt to recolor some stable vertex $v$ with another color $j\in\left[{k}\right]\setminus\left\{{\hat{\sigma}(v)}\right\}$, then we will have to recolor two additional stable vertices $u_{1},u_{2}$ as well. Hence, any attempt to recolor a stable vertex is liable to trigger an avalanche of further recolorings (unless the graph $G$ has an abundance of short cycles, which is well-known not to be the case in the random graph $G(n,m)$ w.h.p.).

The following definition is going to lead to a neat description of the outcome of the whitening process.

A $k$-cover in $G$ is a map $\zeta:V\rightarrow\left\{{0,1,\ldots,k}\right\}$ with the following properties.

There is no edge $e=\left\{{u,v}\right\}$ such that $\zeta(u)=\zeta(v)\neq 0$.

If $\zeta(v)\neq 0$, then $v$ is stable under $\zeta$.

If $\zeta(v)=0$, then there are $i,j\in\left[{k}\right]$, $i\neq j$, such that $v$ does not have a neighbor $u$ with $\zeta(u)=i$ and $v$ has at most one neighbor $w$ with $\zeta(w)=j$.

The concept of covers is very closely related and, in fact, inspired by the properties of certain fixed points of the Survey Propagation message passing procedure . (To my knowledge, the term “cover” has not been used previously in the context of $k$-colorability, although it appears to be in common use in the context of satisfiability .)

Now, the outcome of $\hat{\sigma}$ is the cover characterized by the following two properties.

For all vertices $v$ such that $\hat{\sigma}(v)\neq 0$ we have $\hat{\sigma}(v)=\sigma(v)$.

Subject to i., $|\hat{\sigma}^{-1}(0)|$ is minimum.

Of course, in general the graph $G$ may have many $k$-covers that cannot be obtained from a $k$-coloring via the whitening process. This motivates

A $k$-cover $\zeta$ of $G$ is valid if $G$ has a $k$-coloring $\sigma$ such that $\zeta=\hat{\sigma}$.

To prove Theorem 1.1, we perform a first moment argument for the number of valid $k$-covers. The main task is to show that the all- cover (i.e., $\zeta(v)=0$ for all vertices $v$) is not a valid $k$-cover in $G(n,m)$ w.h.p. To this end, we need to establish a few basic properties that all $k$-colorings of $G(n,m)$ have w.h.p. More precisely, in Section 4 we are going to prove the following via a “standard” first moment argument over $k$-colorings.

Assume that $k\geq k_{0}$ for a sufficiently large constant $k_{0}$. Moreover, assume that $d=2k\ln k-\ln k-c$, with $0\leq c\leq 4$.

W.h.p. all $k$-colorings of $G(n,m)$ satisfy $|\sigma^{-1}(i)|=(1+o_{k}(1))\frac{n}{k}$ for all $i\in\left[{k}\right]$.

In fact, w.h.p. $G(n,m)$ does not have a $k$-coloring $\sigma$ such that $|\sigma^{-1}(i)-n/k|>n/(k\ln^{4}k)$ for more than $\ln^{8}k$ colors $i\in\left[{k}\right]$.

Building upon Proposition 3.4, we will establish the following properties of valid $k$-covers in Section 5.

There is a number $k_{0}$ such that for $k\geq k_{0}$ and $2k\ln k-\ln k-4\leq d\leq 2k\ln k$ any valid $k$-cover $\zeta$ of $G(n,m)$ has the following properties w.h.p.

For all $i\in\left[{k}\right]$ we have $|\zeta^{-1}(i)|=(1+o_{k}(1))n/k$.

In fact, there are no more than $\ln^{9}k$ indices $i\in\left[{k}\right]$ such that $|\zeta^{-1}(i)-n/k|>n/(k\ln^{3}k)$.

Finally, in Section 6 we perform the first moment argument over $k$-covers.

There is $\varepsilon_{k}=o_{k}(1)$ such that for $d\geq 2k\ln k-\ln k-1+\varepsilon_{k}$ w.h.p. the random graph $G(n,m)$ does not have a $k$-cover with properties 1.–3. from Proposition 3.5.

Theorem 1.1 is immediate from Propositions 3.5 and 3.6. Furthermore, we will prove Corollary 1.2 in Section 5.

Proof of Proposition 3.4

The proof of Proposition 3.4 is very much based on standard arguments, reminiscent but unfortunately not (quite) identical to estimates from, e.g., . Suppose $d=2k\ln k-\ln k-c$ with $0\leq c\leq 4$. Throughout this section we work with the random graph $G^{\prime}(n,m)$ with $m$ independent edges.

Let $\nu=(\nu_{1},\ldots,\nu_{k})$ be a $k$-tuple of non-negative integers such that $\sum_{i=1}^{k}\nu_{i}=n$. Let $Z_{\nu}$ be the number of $k$-colorings $\sigma$ of $G^{\prime}(n,m)$ such that $\left|{\sigma^{-1}(i)}\right|=\nu_{i}$ for all $i\in\left[{k}\right]$. Then

Proof. Let $\Sigma_{\nu}$ be the set of all $\sigma:V\rightarrow\left[{k}\right]$ such that $\left|{\sigma^{-1}(i)}\right|=\nu_{i}$ for all $i\in\left[{k}\right]$. By Stirling’s formula,

Let $Z$ be the total number of $k$-colorings of $G^{\prime}(n,m)$. We have

Letting $\mathcal{A}$ be the set of all $k$-tuples $\alpha=(\alpha_{1},\ldots,\alpha_{k})\in^{k}$ such that $\sum_{i=1}^{k}\alpha_{i}=1$, we obtain from (8)

The entropy function $-\sum_{i=1}^{k}\alpha_{i}\ln(\alpha_{i})$ is well-known to attain its maximum at the point \alpha=\frac{1}{k}\mathchoice{\mbox{\boldmath\displaystyle 1}}{\mbox{\boldmath\textstyle 1}}{\mbox{\boldmath\scriptstyle 1}}{\mbox{\boldmath\scriptscriptstyle 1}} with all $k$ entries equal to $1/k$. Furthermore, the sum of squares $\sum_{i=1}^{k}\alpha_{i}^{2}$ attains its minimum at \alpha=\frac{1}{k}\mathchoice{\mbox{\boldmath\displaystyle 1}}{\mbox{\boldmath\textstyle 1}}{\mbox{\boldmath\scriptstyle 1}}{\mbox{\boldmath\scriptscriptstyle 1}} as well. Hence, the term $\frac{d}{2}\ln[1-\sum_{i=1}^{k}\alpha_{i}^{2}]$, and thus (9), is maximized at \frac{1}{k}\mathchoice{\mbox{\boldmath\displaystyle 1}}{\mbox{\boldmath\textstyle 1}}{\mbox{\boldmath\scriptstyle 1}}{\mbox{\boldmath\scriptscriptstyle 1}}. Consequently,

W.h.p. all $k$-colorings $\sigma$ of $G^{\prime}(n,m)$ satisfy $|\sigma^{-1}(i)|=(1+o_{k}(1))\frac{n}{k}$ for all $i\in\left[{k}\right]$, and there is no $k$-coloring $\sigma$ such that $|\sigma^{-1}(i)-1/k|>1/(k\ln^{4}k)$ for more than $\ln^{8}k$ colors $i\in\left[{k}\right]$.

In particular, the first differential $Df$ vanishes at \alpha=\frac{1}{k}\mathchoice{\mbox{\boldmath\displaystyle 1}}{\mbox{\boldmath\textstyle 1}}{\mbox{\boldmath\scriptstyle 1}}{\mbox{\boldmath\scriptscriptstyle 1}}. At this point, the Hessian $D^{2}f=(\frac{\partial^{2}f}{\partial\alpha_{i}\partial\alpha_{j}})_{i,j\in\left[{k-1}\right]}$ is negative-definite, whence \alpha=\frac{1}{k}\mathchoice{\mbox{\boldmath\displaystyle 1}}{\mbox{\boldmath\textstyle 1}}{\mbox{\boldmath\scriptstyle 1}}{\mbox{\boldmath\scriptscriptstyle 1}} is a local maximum. Because the rank-one matrix $((\alpha_{k}-\alpha_{i})\cdot(\alpha_{k}-\alpha_{j}))_{i,j\in\left[{k-1}\right]}$ is positive semidefinite for all $\alpha$, (10) and (11) show that $D^{2}f$ is negative-definite for all $\alpha$. In fact, due to the $-\frac{2d}{1-\left\|{\alpha}\right\|_{2}^{2}}$ term in (10), all its eigenvalues are smaller than $-\frac{d}{1-\left\|{\alpha}\right\|_{2}^{2}}\leq-d$. Therefore, Taylor’s theorem yields that

for all $\alpha$. Hence, Corollary 4.2 implies that

Since $d=(2-o_{k}(1))k\ln k$, the right hand side of (12) is negative if either

$\max_{i\in\left[{k}\right]}|\alpha_{i}-k^{-1}|>(k\ln^{1/3}k)^{-1}$, or

there are more than $\ln^{8}k$ indices $i\in\left[{k}\right]$ such that $|\alpha_{i}-1/k|>(k\ln^{4}k)^{-1}$.

Thus, Markov’s inequality shows that w.h.p. there is no $k$-coloring with either of these properties. $\Box$

Finally, Proposition 3.4 is immediate from Lemma 2.1 and Corollaries 4.2 and 4.3.

Proof of Proposition 3.5

Suppose $d=2k\ln k-\ln k-c$ with $0\leq c\leq 4$. Throughout this section we work with the random graph $G^{\prime}(n,m)$ with $m$ independent edges.

The construction CR1–CR3 has been considered previously to show that a random $k$-coloring of the random graph $G(n,m)$ has many frozen vertices w.h.p. . In the present context we need to perform a rather more thorough analysis of the process CR1–CR3 to show that w.h.p. all $k$-colorings $\sigma$ of $G(n,m)$ induce a non-zero cover $\hat{\sigma}$. To obtain such a strong result, we need to control the large deviations of various quantities, particularly the sizes of the sets $W$, $W_{i}$ and $U$. More precisely, in Section 5.2 we prove

With probability at least $1-\exp(-16n/k)$ the random graph $G^{\prime}(\sigma)$ has the following properties.

For all $i\in\left[{k}\right]$ we have $|W_{i}|\leq\frac{n\ln\ln k}{k\ln k}$.

There are no more than $\ln^{4}k$ indices $i\in\left[{k}\right]$ such that $|W_{i}|\geq\frac{n}{k\ln^{4}k}$.

Moreover, in Section 5.3 we are going to establish

In $G^{\prime}(\sigma)$ we have $\operatorname{P}\left[{\left|{U}\right|>\frac{n\ln\ln k}{k\ln k}}\right]\leq\exp(-10n/k).$

To estimate the size of $Y$ we use the following observation.

W.h.p. the random graph $G^{\prime}(n,m)$ has the following property.

Proof. For any fixed set $\mathcal{Y}$ of size $0<yn\leq\lceil\frac{2n\ln\ln k}{k\ln k}\rceil$ the number $e(\mathcal{Y})$ of edges spanned by $\mathcal{Y}$ in $G^{\prime}(n,m)$ is binomially distributed with mean

Further, by Stirling’s formula the total number of sets $\mathcal{Y}\subset V$ of size $yn$ is

Combining (15) and (16) with the union bound, we obtain

Taking the union bound over all possible sizes $yn$ completes the proof. $\Box$

Proof of Proportion 3.5. By Proposition 3.4 w.h.p. all $k$-colorings $\sigma$ of the random graph $G^{\prime}(n,m)$ satisfy $|\sigma^{-1}(i)|=(1+o_{k}(1))n/k$ for all $i\in\left[{k}\right]$. Let us call such a $k$-coloring $\sigma$ of $G=G^{\prime}(n,m)$ good if it has the following two properties (and bad otherwise):

Step CR1 applied to $G,\sigma$ yields sets $W_{1},\ldots,W_{k},W$ that satisfy the three properties in Lemma 5.1.

The set $U$ created in step CR2 has size $\left|{U}\right|>\frac{n\ln\ln k}{k\ln k}$.

Hence, w.h.p. the random graph $G^{\prime}(n,m)$ does not have a bad $k$-coloring.

If (17) is true and $G^{\prime}(n,m)$ does not have a bad $k$-coloring, then for any $k$-coloring $\sigma$ the set $W\cup Y$ constructed by CR1–CR3 has size at most $|W\cup Y|\leq k^{-0.7}n+\frac{2n\ln\ln k}{k\ln k}\leq nk^{-2/3}$ (the bound on $|W|$ follows from G1). This shows the first property asserted in Proposition 3.5, because the construction CR1–CR3 ensures that the cover $\hat{\sigma}$ obtained from $\sigma$ via the whitening process WH1–WH2 satisfies $\hat{\sigma}(v)=\sigma(v)$ for all $v\in V\setminus(W\cup Y)$. By the same token, the second assertion follows because by G1 and (17) for every color $i\in\left[{k}\right]$ we have

Finally, the G1 and (17) also imply that there cannot be more than $\ln^{9}k$ indices $i\in\left[{k}\right]$ such that $|\sigma^{-1}(i)-n/k|>n/(k\ln^{3}k)$, which is the third assertion. $\Box$

2 Proof of Lemma 5.1

We begin by estimating the number of edges between different color classes. Recall that $V_{i}=\sigma^{-1}(i)$ for $i\in\left[{k}\right]$, and that we are assuming that $|V_{i}|=(1+o_{k}(1))n/k$. Let $\nu_{i}=|V_{i}|$ for $i=1,\ldots,k$.

Proof. Because the edges \mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{1},\ldots,\mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{m} are chosen independently, for any pair $1\leq i<j\leq k$ the random variable $e(V_{i},V_{j})$ has a binomial distribution ${\rm Bin}(m,q_{ij})$, where

Finally, the first assertion follows by taking a union bound over $i,j$. The second assertion follows analogously. $\Box$

Proof of Lemma 5.1. By Lemma 5.4 we may disregard the case that $\min_{1\leq i<j\leq k}e(V_{i},V_{j})\leq\frac{0.99dn}{k^{2}}$. Thus, fix integers $(m_{ij})_{1\leq i<j\leq k}$ such that

Let $\mathcal{M}$ be the event that $e(V_{i},V_{j})=m_{ij}$ for all $1\leq i<j\leq k$.

We need to get a handle on the random variables $(e(v,V_{j}))_{v\in V_{i}}$ (i.e., the number of neighbors of $v$ in $V_{j}$) in the random graph $G^{\prime}(\sigma)$. Given that $\mathcal{M}$ occurs we know that $\sum_{v\in V_{i}}e(v,V_{j})=e(V_{i},V_{j})=m_{ij}$. Furthermore, because $G^{\prime}(\sigma)$ consists of $m$ independent random edges \mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{1},\ldots,\mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{m}, given the event $\mathcal{M}$ the $m_{ij}$ edges between $V_{i}$ and $V_{j}$ are chosen uniformly and independently. Therefore, we can think of the vertices in $V_{i}$ as “bins” and of the $m_{ij}$ edges as randomly tossed “balls”. In particular, the average number of balls that each bin $v\in V_{i}$ receives is $m_{ij}/\nu_{i}$. Crucially, these balls-and-bins experiments are independent for all $i,j$.

In words, the joint probability that the random variables $(e(v,V_{j}))_{v\in V,j\in\left[{k}\right]\setminus\left\{{\sigma(v)}\right\}}$ take certain values given that $\mathcal{M}$ occurs is dominated by the corresponding event for the random variables $(b_{vj})$.

Now, consider the event that there are at least $\kappa=\lceil\ln^{4}k\rceil$ classes $i_{1},\ldots,i_{\kappa}$ such that $|W_{i}|\geq N^{\prime}=\frac{n}{k\ln^{4}k}$. We have

Furthermore, because the random variables $\mathcal{W}_{i_{1}},\ldots,\mathcal{W}_{i_{\kappa}}$ are independent, we obtain from (19) and (24)

With respect to the event $|W|\geq nk^{-0.7}$, observe that by (21) the sum $\mathcal{W}=\sum_{i=1}^{k}\mathcal{W}_{i}$ is stochastically dominated by a binomial random variable with mean $nk^{-0.8}$. Therefore, by (19) and the Chernoff bound

Finally, since the estimates (23), (25), (26) hold for all $\mathcal{M}$, the assertion follows from Bayes’ formula. $\Box$

3 Proof of Lemma 5.2

We begin by estimating the number of edges between the sets $W_{i}$ and the color class $V_{j}$. As before, we let that $V_{i}=\sigma^{-1}(i)$ for $i\in\left[{k}\right]$ and $\nu_{i}=|V_{i}|=(1+o_{k}(1))n/k$ for $i=1,\ldots,k$.

Proof. Fix $1\leq i<j\leq k$. We begin by proving the following statement.

Indeed, for any set $S$ as above the number $e(S,V_{j})$ of edges \mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{i} that join $S$ to $V_{j}$ has a binomial distribution ${\rm Bin}(m,q_{j,S})$, where

the last inequality follows from our assumption that $\nu_{l}=(1+o_{k}(1))n/k$ for all $l\in\left[{k}\right]$. Hence,

Thus, (27) follows from the Chernoff bound. Taking the union bound over all possible sets $S$ of size $|S|\leq\frac{n\ln\ln k}{k\ln k}$, we obtain from (27)

As $\operatorname{P}\left[{|W_{i}|>\frac{n\ln\ln k}{k\ln k}}\right]\leq\exp(-16n/k)$ by Lemma 5.1, the assertion follows from (28). $\Box$

Let $T_{i}$ be the number of vertices $v\in V_{i}$ such that $\max_{j\neq i}e(v,V_{j})>100\ln k$ and let $T=\sum_{i\in\left[{k}\right]}T_{i}$. Then in $G^{\prime}(\sigma)$ we have

Proof. For an integer vector \mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}}=(m_{ij})_{1\leq i<j\leq k} let {\cal E}_{\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}}} be the event that $e(V_{i},V_{j})=m_{ij}$ for all $1\leq i<j\leq k$. Set $m_{ji}=m_{ij}$ for $1\leq i<j\leq k$. By Lemma 5.4 we may confine ourselves to the case that $e(V_{i},V_{j})\leq\frac{2dn}{k^{2}}$ for all $i\neq j$. Thus, fix any $\textstyle m$ such that $m_{ij}\leq\frac{2dn}{k^{2}}$ for all $i<j$. Given {\cal E}_{\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}}}, for each of the $m_{ij}$ edges between color classes $V_{i}$, $V_{j}$ the actual vertex in $V_{i}$ that the edge is incident with is uniformly distributed. Thus, we can think of the vertices $v\in V_{i}$ as bins and of edge $m_{ij}$ edges as balls of color $j$, and our goal is to figure out the probability that bin $v$ contains more than $100\ln k$ balls colored $j$ for some $j\neq i$. Because we are conditioning on {\cal E}_{\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}}}, these balls-and-bins experiments are independent for all color pairs $i\neq j$.

Because the random variables $b_{vj}$ are mutually independent, $\mathcal{T}$ is a sum of independent Bernoulli random variables. Applying the union bound, we thus have

Therefore, (30) shows that $\mathcal{T}$ is stochastically dominated by a binomial random variable ${\rm Bin}(n,k^{-89})$. Consequently, the Chernoff bound yields

Finally, combining (29) and (31) yields the assertion. $\Box$

Proof of Lemma 5.2. Let \mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}=(d_{vj})_{v\in V,j\in\left[{k}\right]\setminus\left\{{\sigma(v)}\right\}} be an integer vector. Moreover, let {\cal E}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}} be the event that $e(v,V_{j})=d_{vj}$ for all $v\in V$, $j\neq\sigma(v)$. We are going to estimate the size of $U$ given that {\cal E}_{\mathchoice{\mbox{\boldmath\displaystyle d}}{\mbox{\boldmath\textstyle d}}{\mbox{\boldmath\scriptstyle d}}{\mbox{\boldmath\scriptscriptstyle d}}} occurs for a vector $\textstyle d$ that is “compatible” with the properties established in Lemmas 5.4–5.6. More precisely, we call $\textstyle d$ feasible if the following conditions are satisfied.

For all $i\neq j$ we have $m_{ij}=\sum_{v\in V_{i}}d_{vj}\geq\frac{dn}{2k^{2}}$. Moreover, $m_{ij}=m_{ji}$.

Let $\mathcal{T}$ be the set of all vertices $v$ such that $\max_{j\neq\sigma(v)}d_{vj}>100\ln k$. Then $\left|{\mathcal{T}}\right|\leq\frac{n}{4k\ln k}$.

By Lemmas 5.4–5.6, we just need to show that for any feasible $\textstyle d$ we have

The sums $\sum_{v\in V_{i}}b_{vj}$ are binomial random variables ${\rm Bin}(m_{ij},w_{ji}/m_{ji})$. Moreover, they are independent for all $i\neq j$. Therefore, Stirling’s formula yields

As $\mathcal{U}\leq\mathcal{T}+\mathcal{U}^{\prime}\leq\mathcal{U}^{\prime}+\frac{n}{4k\ln k}$ by our assumption iii. on $\textstyle d$, (36) implies that $\operatorname{P}\left[{\mathcal{U}\geq\frac{n\ln\ln k}{k\ln k}}\right]\leq\exp(-11n/k)$. Thus, the assertion follows from (33) and (35). $\Box$

Proof of Proposition 3.6

Throughout this section, we let $\zeta:V\rightarrow\left\{{0,1,\ldots,k}\right\}$, $V_{i}=\zeta^{-1}(i)$ and $\nu_{i}=|V_{i}|$ for $i=0,1,\ldots,k$. In addition, we let $\alpha_{i}=\nu_{i}/n$. We always assume that the conditions of Proposition 3.6 hold, namely

$|\zeta^{-1}(i)|=(1+o_{k}(1))n/k$ for all $i\in\left[{k}\right]$.

There are no more than $\ln^{9}k$ indices $i\in\left[{k}\right]$ such that $|\zeta^{-1}(i)-n/k|>n/(k\ln^{3}k)$.

In addition, we assume that $d=2k\ln k-\ln k-c$ for some $0\leq c\leq 4$.

To prove Proposition 3.6 we perform a first moment argument over the number of covers $\zeta$. Let $\mathcal{I}_{\zeta}$ be the event that $V_{1},\ldots,V_{k}$ are independent sets in $G^{\prime}(n,m)$. Moreover, let ${\mathcal{C}}_{\zeta}$ be the event that $\zeta$ is a $k$-cover in $G^{\prime}(n,m)$. Clearly, ${\mathcal{C}}_{\zeta}\subset\mathcal{I}_{\zeta}$, and we begin begin by estimating the probability the latter event. Let $F_{\zeta}=\sum_{j=1}^{k}\alpha_{j}^{2}.$

We have $\frac{1}{n}\ln\operatorname{P}\left[{\mathcal{I}_{\zeta}}\right]=\frac{d}{2}\ln(1-F_{\zeta})$.

Proof. For each of the edges \mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{i} the probability of joining two vertices in $V_{j}$ is $(\nu_{j}/n)^{2}=\alpha_{j}^{2}$. Hence, the probability that \mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{i} does not fall inside any of the classes $V_{1},\ldots,V_{k}$ is equal to $1-F_{\zeta}$. Thus, the assertion follows from the independence of \mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{1},\ldots,\mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{m}. $\Box$

In Section 6.2 we are going to establish the following estimate of the probability of ${\mathcal{C}}_{\sigma}$.

We have $\frac{1}{n}\ln\operatorname{P}\left[{{\mathcal{C}}_{\zeta}|\mathcal{I}_{\zeta}}\right]\leq\sum_{i=0}^{k}\alpha_{i}\ln p_{i}+o(1)$, where

Proof of Proposition 3.6. Let $A$ be the set of all vectors \mathchoice{\mbox{\boldmath\displaystyle\alpha}}{\mbox{\boldmath\textstyle\alpha}}{\mbox{\boldmath\scriptstyle\alpha}}{\mbox{\boldmath\scriptscriptstyle\alpha}}=(\alpha_{0},\ldots,\alpha_{k})\in\left[{0,1}\right]^{k+1} that satisfy the following three conditions (cf. Z1–Z3):

We have $\alpha_{0}\leq k^{-2/3}$ and $\alpha_{i}=(1+o_{k}(1))/k$ for $i=1,\ldots,k$. Indeed, there are no more than $K=\ln^{9}k$ indices $i\in\left[{k}\right]$ such that $|\alpha_{i}-1/k|>k^{-1}\ln^{-3}k$.

$\alpha_{i}n$ is an integer for $i=0,1,\ldots,k$.

For \mathchoice{\mbox{\boldmath\displaystyle\alpha}}{\mbox{\boldmath\textstyle\alpha}}{\mbox{\boldmath\scriptstyle\alpha}}{\mbox{\boldmath\scriptscriptstyle\alpha}}\in A let \mathcal{S}_{\mathchoice{\mbox{\boldmath\displaystyle\alpha}}{\mbox{\boldmath\textstyle\alpha}}{\mbox{\boldmath\scriptstyle\alpha}}{\mbox{\boldmath\scriptscriptstyle\alpha}}} be the set of all maps $\zeta:V\rightarrow\left\{{0,1,\ldots,k}\right\}$ such that $|\zeta^{-1}(i)|=\alpha_{i}n$ for all $i$. Then

Lemmas 6.1 and 6.2 show that for any \zeta\in\mathcal{S}_{\mathchoice{\mbox{\boldmath\displaystyle\alpha}}{\mbox{\boldmath\textstyle\alpha}}{\mbox{\boldmath\scriptstyle\alpha}}{\mbox{\boldmath\scriptscriptstyle\alpha}}},

Given the value of $\alpha_{0}$, the sum $F_{\zeta}=\sum_{i=1}^{k}\alpha_{i}^{2}$ is minimized if $\alpha_{i}=(1-\alpha_{0})/k$ for all $i\in\left[{k}\right]$. Thus,

Using the approximation $\ln(1-z)=-z-z^{2}/2+O(z^{3})$ and recalling that $d=2k\ln k-\ln k-c$, we see that

Furthermore, because $F_{\zeta}\in(0,1)$ and as $\ln(1-z)\leq-z$ for all $z\in(0,1)$, we get

Since $\alpha_{j}=(1+o_{k}(1))/k$ for all $j\in\left[{k}\right]$ by ii. and as $d=2k\ln k-O_{k}(\ln k)$, (40) yields

Moreover, applying condition ii., we obtain from (41)

Further, again because $F_{\zeta}\in(0,1)$ we have

Plugging (39), (42) and (43) into (38), we obtain

Elementary calculus shows that the function $\alpha_{0}\in(0,1)\mapsto-\alpha_{0}(1-\ln\frac{2k\alpha_{0}}{1+4\ln k}+o_{k}(1))$ attains its maximum at $\alpha_{0}=(1+o_{k}(1))\frac{1+4\ln k}{2k}$. Hence, (45) yields

Since condition iii. ensures that $|A|\leq n^{k}=\exp(o(n))$, the assertion follows from (47) by taking the union bound over all \mathchoice{\mbox{\boldmath\displaystyle\alpha}}{\mbox{\boldmath\textstyle\alpha}}{\mbox{\boldmath\scriptstyle\alpha}}{\mbox{\boldmath\scriptscriptstyle\alpha}}\in A and applying Lemma 2.1. $\Box$

2 Proof of Lemma 6.2

Given $\mathcal{I}_{\zeta}$, the pairs \mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{1},\ldots,\mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{m} that constitute the random graph $G^{\prime}(n,m)$ are simply distributed uniformly and independently over the set of all $n^{2}(1-F_{\zeta})$ possible pairs that do not join two vertices in the same class $V_{i}$ for $i=1,\ldots,k$. For each vertex $v$ and each $j\in\left\{{0,1,\ldots,k}\right\}$ let $d_{v,j}$ be the number of pairs \mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{i} such that \mathchoice{\mbox{\boldmath\displaystyle e}}{\mbox{\boldmath\textstyle e}}{\mbox{\boldmath\scriptstyle e}}{\mbox{\boldmath\scriptscriptstyle e}}_{i} contains $v$ together with a vertex from $V_{j}$. Clearly, given $\mathcal{I}_{\zeta}$ we have $d_{v,j}=0$ for all $v\in V_{j}$, $j\in\left[{k}\right]$.

It seems reasonable to expect that the $d_{v,j}$ are asymptotically independent Poisson random variables. To state this precisely, consider a family $(b_{vj})_{v\in V,j\in\left\{{0,1,\ldots,k}\right\}}$ of independent Poisson random variables with means

Let $\mathcal{B}_{\zeta}$ be the event that

for any $v\in V_{0}$ there exist $i,j\in\left[{k}\right]$, $i\neq j$ such that $b_{vi}=0$ and $b_{vj}\leq 1$ and

for any $1\leq i<j\leq k$ and any $v\in V_{i}$ we have $b_{vj}>1$.

The key step in the proof (somewhat reminiscent of the Poisson cloning model ) is to establish the following.

We have $\operatorname{P}\left[{{\mathcal{C}}_{\zeta}|\mathcal{I}_{\zeta}}\right]\leq\exp(o(n))\cdot\operatorname{P}\left[{\mathcal{B}_{\zeta}}\right]$.

To prove Lemma 6.3 we consider a further event. Set $B_{ij}=\sum_{v\in V_{i}}b_{vj}$ for $i,j\in\left\{{0,1,\ldots,k}\right\}$, $(i,j)\neq(0,0)$. Being sums of independent Poisson variables, the random variables $B_{ij}$ are Poisson as well, with means

In addition, let $B_{00}$ be a random variable that is independent of all of the above such that $\frac{1}{2}B_{00}$ has distribution ${\rm Po}(\alpha_{0}^{2}m/(1-F_{\zeta}))$. (In particular, $B_{00}$ takes even values only.) Now, let $\mathcal{V}$ be the event that

$\frac{1}{2}B_{00}+\sum_{0\leq i<j\leq k}B_{ij}=m$.

We have $\operatorname{P}\left[{\mathcal{V}}\right]=\exp(o(n))$.

Proof of Lemma 6.3. Let \mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}}=(m_{ij})_{i,j\in\left\{{0,1,\ldots,k}\right\}} be a family of non-negative integers such that

$m_{ii}=0$ for $i\in\left[{k}\right]$ and

Let \mathcal{M}_{\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}}} be the event that

Analogously, let \mathcal{M}_{\mathchoice{\mbox{\boldmath\displaystyle m}}{\mbox{\boldmath\textstyle m}}{\mbox{\boldmath\scriptstyle m}}{\mbox{\boldmath\scriptscriptstyle m}}}^{\prime} be the event that