The condensation phase transition in random graph coloring

Introduction

Let $G(n,p)$ denote the random graph on the vertex set $V=\left\{{1,\ldots,n}\right\}$ obtained by connecting any two vertices with probability $p\in$ independently. Throughout the paper, we are concerned with the setting that $p=d/n$ for a number $d>0$ that remains fixed as $n\rightarrow\infty$. We say that $G(n,d/n)$ has a property with high probability (‘w.h.p.’) if its probability converges to $1$ as $n\rightarrow\infty$.

The study of random constraint satisfaction problems started with experimental work in the 1990s, which led to two hypotheses . First, that in problems such as random $k$-SAT or random graph coloring there is a satisfiability threshold, i.e., a critical “constraint density” below which the instance admits a solution and above which it does not w.h.p. Second, that this threshold is associated with the algorithmic “difficulty” of actually computing a solution, where “difficulty” has been quantified in various ways, albeit not in the formal sense of computational complexity. These findings have led to a belief that random instances of $k$-SAT or graph $k$-colorability near the threshold for the existence of solutions are challenging algorithmic benchmarks, at the very least.

In addition, inspired by predictions from statistical physics, the geometry of the set of solutions of random $k$-SAT or $k$-colorability instances has been investigated . The result is that at a certain point well before the satisfiability threshold the set of solutions shatters into a multitude of well-separated “clusters”. Inside each cluster, all solutions agree on most of the variables/vertices, the so-called “frozen” ones. The average degree $d$ at which these “frozen clusters” arise (roughly) matches the point up to which efficient algorithms provably find solutions. Hence, on the one hand it is tempting to think that there is a connection between clustering and the computational “difficulty” of finding a solution . On the other hand, physicists have suggested new message passing algorithms specifically to cope with a clustered geometry . A satisfactory analysis of these algorithms remains elusive.

The physics predictions are not merely circumstantial or experimental findings. They derive from a non-rigorous but systematic formalism called the cavity method . This technique yields, among other things, a prediction as to the precise location of the $k$-SAT or $k$-colorability threshold. But perhaps even more remarkably, according to the cavity method shortly before the threshold for the existence of solutions there occurs another phase transition called condensation . This phase transition marks a further change in the geometry of the solution space. While prior to the condensation phase transition each cluster contains only an exponentially small fraction of all solutions, thereafter a sub-exponential number of clusters contain a constant fraction of the entire set of solutions. As we will see in Section 3 below, the condensation phenomenon seems to hold the key to a variety of problems, including that of finding the $k$-colorability threshold and of analyzing message passing algorithms rigorously. More generally, the physicists’ cavity method is extremely versatile. It has been used to put forward tantalizing conjectures in a variety of areas, including coding theory, probabilistic combinatorics, compressive sensing and, of course, mathematical physics (see for an overview). Hence the importance of providing a rigorous foundation for this technique.

Results

In this paper we prove that, indeed, a condensation phase transition occurs in random graph coloring, and that it occurs at the precise location predicted by the cavity method. This is the first rigorous result to determine the exact location of the condensation transition in a model of this kind. Additionally, the proof yields a direct combinatorial explanation of how this phase transition comes about.

To state the result, let us denote by $Z_{k}(G)$ the number of $k$-colorings of a graph $G$. We would like to study the “typical value” of $Z_{k}(G(n,d/n))$ in the limit as $n\rightarrow\infty$. As it turns out, the correct scaling of this quantity (to obtain a finite limit) isIn the physics literature, one typically considers $n^{-1}\ln Z$ instead of $Z^{1/n}$, where $Z$ is the so-called “partition function”. We work with the $n$th root because our “partition function” $Z_{k}$ may be equal to .

for any $d\in(d_{0}-\varepsilon,d_{0}+\varepsilon)$ the limit $\Phi_{k}(d)$ exists, and

the map $d\in(d_{0}-\varepsilon,d_{0}+\varepsilon)\mapsto\Phi_{k}(d)$ has an expansion as an absolutely convergent power series around $d_{0}$.

If $d_{0}$ fails to be smooth, we say that a phase transition occurs at $d_{0}$.

For a smooth $d_{0}$ the sequence of random variables $(Z_{k}(G(n,d_{0}/n))^{1/n})_{n}$ converges to $\Phi_{k}(d_{0})$ in probability. This follows from a concentration result for the number of $k$-colorings from . Hence, $\Phi_{k}(d)$ really captures the “typical” value of $Z_{k}(G(n,d/n)$ (up to a sub-exponential factor).

Further, let $\mathcal{P}$ be the set of all probability measures on $\Omega$. For each $\mu\in\Omega$ let $\delta_{\mu}\in\mathcal{P}$ denote the Dirac measure that puts mass one on the single point $\mu$. In particular, \delta_{k^{-1}\mathchoice{\mbox{\boldmath\displaystyle 1}}{\mbox{\boldmath\textstyle 1}}{\mbox{\boldmath\scriptstyle 1}}{\mbox{\boldmath\scriptscriptstyle 1}}}\in\mathcal{P} signifies the measure that puts mass one on the uniform distribution k^{-1}\mathchoice{\mbox{\boldmath\displaystyle 1}}{\mbox{\boldmath\textstyle 1}}{\mbox{\boldmath\scriptstyle 1}}{\mbox{\boldmath\scriptscriptstyle 1}}=(1/k,\ldots,1/k). For $\pi\in\mathcal{P}$ and $\gamma\geq 0$ let

Further, define a map $\mathcal{F}_{d,k}:\mathcal{P}\rightarrow\mathcal{P}$, $\pi\mapsto\mathcal{F}_{d,k}[\pi]$ by letting

The main theorem is in terms of a fixed point of the map $\mathcal{F}_{d,k}$, i.e., a point $\pi^{*}\in\mathcal{P}$ such that $\mathcal{F}_{d,k}[\pi^{*}]=\pi^{*}$. In general, the map $\mathcal{F}_{d,k}$ has several fixed points. Hence, we need to single out the correct one. For $h\in\left[{k}\right]$ let $\delta_{h}\in\Omega$ denote the vector whose $h$th coordinate is one and whose other coordinates are (i.e., the Dirac measure on $h$). We call a measure $\pi\in\mathcal{P}$ frozen if $\pi(\left\{{\delta_{1},\ldots,\delta_{k}}\right\})\geq 2/3$; in words, the total probability mass concentrated on the $k$ vertices of the simplex $\Omega$ is at least $2/3$.

There exists a constant $k_{0}\geq 3$ such that for any $k\geq k_{0}$ the following holds. If $d\geq(2k-1)\ln k-2$, then $\mathcal{F}_{d,k}$ has precisely one frozen fixed point $\pi^{*}_{d,k}$. Further, the function

Thus, if $d$ is smooth, then $\Phi_{k}(d)<k\cdot(1-1/k)^{d/2}.$

The above formulas are derived systematically via the cavity method . For instance, the functional $\phi_{d,k}$ is a special case of a general formula, the so-called “Bethe free entropy”. Moreover, the map $\mathcal{F}_{d,k}$ is the distributional version of the “Belief Propagation” operator. In effect, the predictions as to the condensation phase transitions in other problems look very similar to the above. Consequently, it can be expected that the proof technique developed in the present work carries over to many other problems.

2. The cluster size

i.e., $\rho_{ij}(\sigma,\tau)$ is the fraction of vertices colored $i$ under $\sigma$ and $j$ under $\tau$. Now, define the cluster of $\sigma$ in $G$ as

Suppose that $\sigma,\tau$ are such that $|\sigma^{-1}(i)|,|\tau^{-1}(i)|\sim n/k$ for all $i\in\left[{k}\right]$; most $k$-colorings of $G(n,d/n)$ have this property w.h.p. . Then $\tau\in{\mathcal{C}}(G,\sigma)$ means that a little over $50\%$ of the vertices with color $i$ under $\sigma$ also have color $i$ under $\tau$. To this extent, ${\mathcal{C}}(G,\sigma)$ comprises of colorings “similar” to $\sigma$. In fact, for the range of $d$ that we are interested in, this definition coincides w.h.p. with that from (“colorings that can be reached from $\sigma$ by iteratively altering the colors of $o(n)$ vertices at time”).

Discussion and related work

In this section we discuss some relevant related work and also explain the impact of Theorem 2.1 on some questions that have come up in the literature.

where $\varepsilon_{k},\delta_{k}\rightarrow 0$ as $k\rightarrow\infty$. The upper bound is by the “first moment” method . The lower bound rests on a “second moment” argument , which improves a landmark result of Achlioptas and Naor .

2. “Quiet planting?”

3. Message passing algorithms

The cavity method has inspired new “message passing” algorithms by the name of Belief/Survey Propagation Guided Decimation . Experiments on random graph $k$-coloring instances for small values of $k$ indicate an excellent performance of these algorithms . However, whether these experimental results are reliable and/or extend to larger $k$ remains shrouded in mystery.

For instance, Belief Propagation Guided Decimation can most easily be described in terms of list colorings. Suppose that $G$ is a given input graph. Initially, the list of colors available to each vertex is the full set $\left[{k}\right]$. The algorithm chooses a color for one vertex at a time as follows. First, it performs a certain fixed point iteration to approximate for each vertex the marginal probability of taking some color $i$ in a randomly chosen proper list coloring of $G$. Then, a vertex $v$ is chosen, say, uniformly at random and a random color $i$ is chosen from the (supposed) approximation to its marginal distribution. The color list of $v$ is reduced to the singleton $\left\{{i}\right\}$, color $i$ gets removed from the lists of all the neighbors of $v$, and we repeat. The algorithm terminates when either for each vertex a color has been chosen (“success”) or the list of some vertex becomes empty (“failure”). Ideally, if at each step the algorithm manages to compute precisely the correct marginal distribution, the result would be a uniformly random $k$-coloring of the input graph. Of course, generating such a random $k$-coloring is $\#P$-hard in the worst case, and the crux is that the aforementioned fixed point iteration may or may not produce a good approximation to the actual marginal distribution.

Perhaps the most plausible stab at understanding Belief Propagation Guided Decimation is the non-rigorous contribution . Roughly speaking, the result of the Belief Propagation fixed point iteration after $t$ iterations can be expected to yield a good approximation to the actual marginal distribution iff there is no condensation among the remaining list colorings. If so, one should expect that the algorithm actually finds a $k$-coloring if condensation does not occur at any step $0\leq t\leq n$. Thus, we look at a two-dimensional “phase diagram” parametrised by the average degree $d$ and the time $t/n$. We need to identify the line that marks the (suitably defined) condensation phase transition in this diagram. Theorem 2.1 deals with the case $t=0$, and it would be most interesting to see if the present techniques extend to $t\in(0,1)$. Attempts at (rigorously) analysing message passing algorithms along these lines have been made for random $k$-SAT, but the current results are far from precise .

4. The physics perspective

In physics terminology the random graph coloring problem is an example of a “diluted mean-field model of a disordered system”. The term “mean-field” refers to the fact that there is no underlying lattice geometry, while “diluted” indicates that the average degree in the underlying graph is bounded. Moreover, “disordered systems” reflects that the model involves randomness (i.e., the random graph). Diluted mean-field models are considered a better approximation to “real” disordered systems (such as glasses) than models where the underlying graph is complete, such as the Sherrington-Kirkpatrick model . From the viewpoint of physics, the question of whether “disordered systems” exhibit a condensation phase transition can be traced back to Kauzmann’s experiments in the 1940s . In models where the underlying graph is complete, physicsts predicted an affirmative answer in the 1980s , and this has long been confirmed rigorously .

With respect to “diluted” models, Coja-Oghlan and Zdeborova showed that a condensation phase transition exists in random $r$-uniform hypergraph $2$-coloring. Furthermore, determines the location of the condensation phase transition up to an error $\varepsilon_{r}$ that tends to zero as the uniformity $r$ of the hypergraph becomes large. By contrast, Theorem 2.1 is the first result that pins down the exact condensation phase transition in a diluted mean-field model.

Technically, we build upon some of the techniques that have been developed to study the “geometry” of the set of $k$-colorings of the random graph and add to this machinery. Among the techniques that we harness is the “planting trick” from (which, in a sense, we are going to “put into reverse”), the notion of a core , techniques for proving the existence of “frozen variables” , and a concentration argument from . Additionally, our proof directly incorporates some of the physics calculations from [31, Appendix C]. That said, the cornerstone of the present work is a novel argument that allows us to connect the distributional fixed point problem from rigorously with the geometry of the set of $k$-colorings.

From here on we tacitly assume that $k\geq k_{0}$ for some large enough constant $k_{0}$ and that $n$ is sufficiently large. We use the standard $O$-notation when referring to the limit $n\rightarrow\infty$. Thus, $f(n)=O(g(n))$ means that there exist $C>0$, $n_{0}>0$ such that for all $n>n_{0}$ we have $|f(n)|\leq C\cdot|g(n)|$. In addition, we use the standard symbols $o(\cdot),\Omega(\cdot),\Theta(\cdot)$. In particular, $o(1)$ stands for a term that tends to as $n\rightarrow\infty$.

Outline

Because the $n$th root sits inside the expectation, the quantity

is difficult to calculate for general values of $d$. However for $d\in[0,1)$, $\Phi_{k}(d)$ is easily understood. In fact, the celebrated result of Erdős and Rényi implies that for $d\in[0,1)$ the random graph $G(n,d/n)$ is basically a forest. Moreover, the number of $k$-colorings of a forest with $n$ vertices and $m$ edges is well-known to be $k^{n}(1-1/k)^{m}$. Since $G(n,d/n)$ has $m\sim dn/2$ edges w.h.p., we obtain

As $Z_{k}(G)^{1/n}\leq k$ for any graph on $n$ vertices, (4.1) implies that

Clearly, the function $d\mapsto k(1-1/k)^{d/2}$ is analytic on all of $(0,\infty)$. Therefore, the uniqueness of analytic continuations implies that the least $d>0$ where the limit $\Phi_{k}(d)$ either fails to exist or strays away from $k(1-1/k)^{d/2}$ is going to be a phase transition. Hence, we let

The upper bound (3.1) on the $k$-colorability threshold implies that for $d>(2k-1)\ln k$, $G(n,d/n)$ fails to be $k$-colorable w.h.p. Hence, for such $d$ we have $Z_{k}(G(n,d/n))=0$ w.h.p., and thus $\Phi_{k}(d)=0$. By contrast, $k(1-1/k)^{d/2}>0$ for any $d>0$. ∎

In this latter experiment, we first choose a map \mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}:\left[{n}\right]\rightarrow\left[{k}\right] uniformly at random. Then, we generate a graph G(n,p^{\prime},\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}) on $\left[{n}\right]$ by connecting any two vertices $v,w\in\left[{n}\right]$ such that \mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}(v)\neq\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}(w) with probability $p^{\prime}$ independently. If $p^{\prime}=dk/(k-1)$ is chosen so that the expected number of edges is the same as in $G(n,d/n)$ and if $\Phi_{k}(d)=k(1-1/k)^{d/2}$, then this so-called planted model is a good approximation to the “difficult” experiment of first choosing $G(n,d/n)$ and then picking a random $k$-coloring. In particular, we expect that

Assume that $(2k-1)\ln k-2\leq d\leq(2k-1)\ln k$ and set

The proof of Proposition 4.3 is given in Section 6.

2. The second thread.

Our next aim is to “solve” the fixed point problem for $\mathcal{F}_{d,k}$ to an extent that gives the fixed point an explicit combinatorial interpretation. This combinatorial interpretation is in terms of a certain random tree process, associated with a concept of “legal colorings”. Specifically, we consider a multi-type Galton-Watson branching process. Its set of types is

Finally, consider a rooted, decorated tree $(T,\vartheta,v_{0})$ and let $\textstyle\tau$ be a legal coloring of $(T,\vartheta,v_{0})$ chosen uniformly at random. Then the color \mathchoice{\mbox{\boldmath\displaystyle\tau}}{\mbox{\boldmath\textstyle\tau}}{\mbox{\boldmath\scriptstyle\tau}}{\mbox{\boldmath\scriptscriptstyle\tau}}(v_{0}) of the root is a random variable with values in $\left[{k}\right]$. Let $\mu_{T,\vartheta,v_{0}}\in\Omega$ denote its distribution. Clearly, $\mu_{T,\vartheta,v_{0}}$ is invariant under isomorphisms. Consequently, the distribution \mu_{\mathchoice{\mbox{\boldmath\displaystyle T}}{\mbox{\boldmath\textstyle T}}{\mbox{\boldmath\scriptstyle T}}{\mbox{\boldmath\scriptscriptstyle T}}_{d,k,\mathchoice{\mbox{\boldmath\displaystyle q}}{\mbox{\boldmath\textstyle q}}{\mbox{\boldmath\scriptstyle q}}{\mbox{\boldmath\scriptscriptstyle q}}}} of the color of the root of a tree in the random isomorphism class \mathchoice{\mbox{\boldmath\displaystyle T}}{\mbox{\boldmath\textstyle T}}{\mbox{\boldmath\scriptstyle T}}{\mbox{\boldmath\scriptscriptstyle T}}_{d,k,\mathchoice{\mbox{\boldmath\displaystyle q}}{\mbox{\boldmath\textstyle q}}{\mbox{\boldmath\scriptstyle q}}{\mbox{\boldmath\scriptscriptstyle q}}} is a well-defined $\Omega$-valued random variable. Let \pi_{d,k,\mathchoice{\mbox{\boldmath\displaystyle q}}{\mbox{\boldmath\textstyle q}}{\mbox{\boldmath\scriptstyle q}}{\mbox{\boldmath\scriptscriptstyle q}}}\in\mathcal{P} denote its distribution. Then we can characterise the frozen fixed point of $\mathcal{F}_{d,k}$ as follows.

has a unique fixed point $q^{*}$ in the interval $[2/3,1]$. Moreover, with

The map $\mathcal{F}_{d,k}$ has precisely one frozen fixed point, namely \pi_{d,k,\mathchoice{\mbox{\boldmath\displaystyle q}}{\mbox{\boldmath\textstyle q}}{\mbox{\boldmath\scriptstyle q}}{\mbox{\boldmath\scriptscriptstyle q}}^{*}}.

The function (4.8) and its fixed point also occur in the physics work . The proof of Proposition 4.4 can be found in Section 7.

3. Tying up the threads

Computing the cluster size hinges on a close understanding of its combinatorial structure. As hypothesised in physics work and established rigorously in , typically many vertices $v$ are “frozen” in {\mathcal{C}}(\mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}},\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}), i.e., $\tau(v)=\tau^{\prime}(v)$ for any two colorings \tau,\tau^{\prime}\in{\mathcal{C}}(\mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}},\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}). More generally, we consider for each vertex $v$ the set

By construction, each coloring \tau\in{\mathcal{C}}(\mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}},\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}) is a legal coloring of the decorated graph $\textstyle G$. Conversely, we will see that w.h.p. any legal coloring of (\mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}},\vartheta) belongs to the cluster {\mathcal{C}}(\mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}},\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}). Hence, computing the cluster size |{\mathcal{C}}(\mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}},\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}})| amounts to calculating the number \mathcal{Z}(\mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}},\vartheta) of legal colorings of \mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}},\vartheta.

Thus, we just need to compute \mathcal{Z}(\widetilde{\mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}}},\vartheta). This task is much easier than computing \mathcal{Z}(\mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}},\vartheta) directly because \widetilde{\mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}}} turns out to have significantly fewer edges than $\textstyle G$ w.h.p. More precisely, w.h.p. \widetilde{\mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}}} (mostly) consists of connected components that are trees of bounded size. In fact, in a certain sense the distribution of the tree components converges to that of the decorated random tree \mathchoice{\mbox{\boldmath\displaystyle T}}{\mbox{\boldmath\textstyle T}}{\mbox{\boldmath\scriptstyle T}}{\mbox{\boldmath\scriptscriptstyle T}}_{d,k,\mathchoice{\mbox{\boldmath\displaystyle q}}{\mbox{\boldmath\textstyle q}}{\mbox{\boldmath\scriptstyle q}}{\mbox{\boldmath\scriptscriptstyle q}}_{*}}. In effect, we obtain

Groundwork: the first and the second moment method

In this section we prove Proposition 4.2 and also lay the foundations for the proof of Proposition 4.3. Throughout this section, we always set $m=\lceil dn/2\rceil$ and we let $G(n,m)$ denote a random graph with vertex set $V=[n]=\left\{{1,\ldots,n}\right\}$ and with precisely $m$ edges chosen uniformly at random.

We start by deriving an upper bound on $\Phi_{k}(d)$ by computing the expected number of $k$-colorings. To avoid fluctuations of the total number of edges, we work with the $G(n,m)$ model.

Lemma 5.1 is folklore. We carry the proof out regardless to make a few observations that will be important later. For a map $\sigma:\left[{n}\right]\rightarrow\left[{k}\right]$ let

be the number of “forbidden pairs” of vertices that are colored the same under $\sigma$. By convexity,

As there are $k^{n}$ possible maps $\sigma$ in total, the linearity of expectation and (5.3) imply

As a further consequence of Lemma 5.1, we obtain

Now, let $c>0$ and set $d=c-\varepsilon$ for some $\varepsilon>0$. The number of edges in $G(n,c/n)$ is binomially distributed with mean $(1+o(1))cn/2=m+\Omega(n)$. Hence, by the Chernoff bound the probability of the event $\mathcal{A}$ that $G(n,c/n)$ has at least $m$ edges tends to $1$ as $n\rightarrow\infty$. Because adding further edges can only decrease the number of $k$-colorings and since the number of $k$-colorings is trivially bounded by $k^{n}$, we obtain from (5.5) that

2. The second moment lower bound.

Thus, if $\sigma$ is a balanced, separable $k$-coloring, then for any color $i$ and for any other balanced $k$-coloring $\tau$ in the cluster of $\sigma$, a $1-\kappa+o(1)$-fraction of the vertices colored $i$ under $\sigma$ are colored $i$ under $\tau$ as well. In particular, the clusters of any two such colorings are either disjoint or identical.

Let $G$ be a graph with $n$ vertices and $m$ edges. A $k$-coloring $\sigma$ of $G$ is tame if

Furthermore, there exists $\varepsilon_{k}=o_{k}(1)$ such that (5.6) is satisfied if $d\leq(2k-1)\ln k-2\ln 2-\varepsilon_{k}$.

As fleshed out in , together with the sharp threshold result from , Lemma 5.5 implies that $G(n,d/n)$ is $k$-colorable w.h.p. if $d\leq(2k-1)\ln k-2\ln 2-\varepsilon_{k}$. Here we are going to combine Lemma 5.5 with the following variant of that sharp threshold result to obtain a lower bound on the number of $k$-colorings.

For any $k\geq 3$ and for any real $\xi>0$ there is a sequence $d_{k,\xi}(n)$ such that for any $\varepsilon>0$ the following holds.

If $p(n)<(1-\varepsilon)d_{k,\xi}(n)/n$, then $Z_{k}(G(n,p(n)))\geq\xi^{n}$ w.h.p.

If $p(n)>(1+\varepsilon)d_{k,\xi}(n)/n$, then $Z_{k}(G(n,p(n)))<\xi^{n}$ w.h.p.

Further, pick and fix $d_{*}<\hat{d}<d^{*}$ such that $k(1-1/k)^{\hat{d}/2}>k(1-1/k)^{d_{*}/2}-\varepsilon_{*}$ and $\xi$ such that

We are going to use Lemmas 5.5 and 5.6 to establish a lower bound on $Z_{k}(G(n,d_{*}/n))$ that contradicts (5.7). By the Paley-Zygmund inequality and because (5.6) holds for any $d^{*}-\varepsilon<d<d^{*}$,

Further, because (5.6) is true for any $d^{*}-\varepsilon<d<d^{*}$ and $\xi<k(1-1/k)^{d/2}$ for any $d<\hat{d}<d^{*}$, we see that

Since the number of edges in $G(n,d/n)$ has a binomial distribution with mean $m$, with probability at least $1/3$ the number of edges in $G(n,d/n)$ does not exceed $m$. Therefore, (5.11) implies that

Moreover, (5.12) entails that the sequence $d_{k,\xi}(n)$ from Lemma 5.6 satisfies $\liminf d_{k,\xi}(n)\geq\hat{d}$. Therefore,

Since $d_{*}<\hat{d}$, (5.13) entails that

3. Proof of Proposition 4.2

If $d_{1}\in D_{*}$ and $d_{2}>d_{1}$, then $d_{2}\in D_{*}$. Similarly, if $d_{1}\in D^{*}$ and $d_{2}>d_{1}$, then $d_{2}\in D^{*}$.

Let $0<d_{1}<d_{2}$ and let $q\sim(d_{2}-d_{1})/n$ be such that $d_{1}/n+(1-d_{1}/n)q=d_{2}/n$. Let us denote the random graph $G(n,d_{1}/n)$ by $G_{1}$. Furthermore, let $G_{2}$ be a random graph obtained from $G_{1}$ by joining any two vertices that are not already adjacent in $G_{1}$ with probability $q$ independently. Then $G_{2}$ is identical to $G(n,d_{2}/n)$, because in $G_{2}$ any two vertices are adjacent with probability $d_{1}/n+(1-d_{1}/n)q=d_{2}/n$ independently. Set $N={{n}\choose{2}}$.

Let $e(G_{i})$ signify the number of edges in $G_{i}$ for $i=1,2$. Because $e(G_{i})$ is a binomial random variable with mean $\mu_{i}=\frac{d_{i}}{n}\cdot N=nd_{i}/2+O(1)$, the Chernoff bound implies that

Further, since $Z_{k}^{1/n}\leq k$ with certainty, (5.15) implies that

Hence, by (5.16), Jensen’s inequality and (5.17)

Hence, the first and the third assertion are immediate from Lemma 5.8.

The planted model

The aim in this section is to prove Proposition 4.3. The proof of the first part is fairly straightforward. More precisely, in Section 6.2 we are going to establish

Let $d>0$. Assume that there exists a sequence $({\mathcal{E}}_{n})_{n\geq 1}$ of events such that

We prove Lemma 6.2 in Section 6.3. Hence, assuming that the typical cluster size in the planted model is “too big” w.h.p., we need to exhibit events ${\mathcal{E}}_{n}$ such that (6.1) holds. An obvious choice seems to be

But (6.1) requires that the probability that ${\mathcal{E}}_{n}$ occurs in $G(n,m,\sigma)$ is exponentially small, and neither the cluster size nor $Z_{k}$ are known to be sufficiently concentrated to obtain such an exponentially small probability.

Therefore, we define the events ${\mathcal{E}}_{n}$ by means of another random variable. For a graph $G=(V,E)$ and a map $\sigma:V\rightarrow\left[{k}\right]$ let $\mathcal{H}_{G}(\sigma)$ be the number of edges $\left\{{v,w}\right\}$ of $G$ such that $\sigma(v)=\sigma(w)$. In words, $\mathcal{H}_{G}(\sigma)$ is the number of edges of $G$ that are monochromatic under $\sigma$. Furthermore, given $\beta>0$ let

a quantity known as the partition function of the $k$-spin Potts antiferromagnet on $G$ at inverse temperature $\beta$.

For large $\beta$ there is a stiff “penalty factor” of $\exp(-\beta)$ for any monochromatic edge. Thus, we expect that $Z_{\beta,k}$ becomes a good proxy for $Z_{k}$ as $\beta\rightarrow\infty$. At the same time, $\ln Z_{\beta,k}$ enjoys a Lipschitz property. Namely, suppose that we obtain a graph $G^{\prime}$ from $G$ by either adding or removing a single edge. Then

Due to this Lipschitz property, one can easily show that $\ln Z_{\beta,k}$ is tightly concentrated. More precisely, we have

For any fixed $d>0$, $\varepsilon>0$ there is $\alpha>0$ such that the following is true. Suppose that $(\sigma_{n})_{n\geq 1}$ is a sequence of maps $\left[{n}\right]\rightarrow\left[{k}\right]$. Then for all large enough $n$,

This is immediate from the Lipschitz property (6.2) and McDiarmid’s inequality [21, Theorem 3.8]. ∎

Furthermore, in Section 6.4 we show that Lemma 6.3 implies

Assume that $d$ is such that (4.7) holds. Then there exist $z,\beta>0$ such that

Finally, Proposition 4.3 is immediate from Lemmas 6.1, 6.2 and 6.4.

2. Proof of Lemma 6.1

Suppose that $(2k-1)\ln k-2\leq d\leq(2k-1)\ln k$. Let $p^{\prime}$ be as in (4.5). Then the planted coloring $\textstyle\sigma$ is separable in G(n,p^{\prime},\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}) w.h.p.

If (4.6) holds, then there exists $\varepsilon>0$ such that with $p^{\prime}$ from (4.5) we have

Pick a number $d^{*}>d$ such that with $m^{*}=\lceil d^{*}n/2\rceil$ we have

We claim that if we choose \mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}:\left[{n}\right]\rightarrow\left[{k}\right] uniformly at random and independently a random graph $G(n,m^{*})$, then

Further, set $d^{\prime\prime}=kd^{*}/(k-1)$ and let $p^{\prime\prime}=d^{\prime\prime}/n>p^{\prime}$. Then we can think of G(n,p^{\prime\prime},\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}) as being obtained from G(n,p^{\prime},\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}) by adding further random edges. More precisely, let $\mathcal{A}$ be the event that G(n,p^{\prime\prime},\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}) contains precisely $m^{*}$ edges and set

Since adding edges can only decrease the cluster size, (6.5) entails

As (6.6)–(6.8) yield $\liminf_{n\rightarrow\infty}p_{n}>0$, we obtain (6.4)

3. Proof of Lemma 6.2

Indeed, the number $e(G(n,d^{*}/n))$ of edges of $G(n,d^{*}/n)$ is binomially distributed with mean $(1+o(1))d^{*}n/2$. Since $d,d^{*}$ are independent of $n$ and $d^{*}>d$, the Chernoff bound implies that

Further, if we condition on the event that $m^{*}=e(G(n,d^{*}/n))>m$, then we can think of $G(n,d^{*}/n)$ as follows: first, create a random graph $G(n,m)$; then, add another $m^{*}-m$ random edges. Since the addition of further random edges cannot increase the number of $k$-colorings, (6.10)

Taking $n\rightarrow\infty$, and assuming that $d^{*}>d$ is sufficiently close to $d$, we conclude that

Hence, for any $\varepsilon>0$ there is $d^{*}\in(d,d+\varepsilon)$ such that $d^{*}\in D^{*}$. Thus, (6.9) follows from Lemma 5.8. ∎

Assuming the existence of $d$ and $({\mathcal{E}}_{n})_{n}$ as in Lemma 6.2, we are going to argue that

Then the assertion follows from Lemma 6.6.

Furthermore, by the linearity of expectation,

To estimate the last factor, we use (5.2) and Stirling’s formula, which yield

Plugging this estimate into (6.13) and recalling that $\textstyle\sigma$ is a random map $\left[{n}\right]\rightarrow\left[{k}\right]$, we obtain

thereby completing the proof of (6.11). ∎

4. Proof of Lemma 6.4

Let $d>0$. For any $\varepsilon>0$ there exists $\beta>0$ such that

For any fixed number $\gamma>0$ we can choose $\beta(\gamma)>0$ so large that $\ln k-\beta\gamma<0$. Now, let $\mathcal{M}(G(n,m))$ be the set of all $\sigma:\left[{n}\right]\rightarrow\left[{k}\right]$ such that at least $\gamma n$ edges are monochromatic under $\sigma$, and let $\overline{\mathcal{M}}(G(n,m))$ contain all $\sigma\not\in\mathcal{M}(G(n,m))$. Then

Further, if $\sigma\in\overline{\mathcal{M}}(G(n,m))$, then $\sigma$ is a $k$-coloring of a subgraph of $G(n,m)$ containing $m-\gamma n$ edges. Hence, we obtain from Stirling’s formula that for $\gamma=\gamma(\varepsilon)>0$ small enough,

Assume that (4.7) is true. Then there exist a fixed number $\varepsilon>0$, a sequence $\sigma_{n}$ of balanced maps $\left[{n}\right]\rightarrow\left[{k}\right]$ and a sequence $\mu_{n}$ of numbers satisfying $|\mu_{n}-dn/2|\leq\sqrt{n}$ such that

Let $\mathcal{A}$ be the event that the number of edges in the random graph G(n,p^{\prime},\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}) differs from $dn/2$ by at most $\sqrt{n}$. Let $N={{n}\choose{2}}$. For any balanced $\sigma:\left[{n}\right]\rightarrow\left[{k}\right]$ the expected number of edges in G(n,p^{\prime},\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}) is

Since the number of edges in G(n,p^{\prime},\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}) is a binomial random variable, (6.17) shows together with the central limit theorem that there exists a fixed $\gamma>0$ such that for sufficiently large $n$

Furthermore, by Stirling’s formula there is an $n$-independent number $\delta>0$ such that for sufficiently large $n$ we have

Then (4.7) and (6.20) imply that $\lim_{n\rightarrow\infty}p(\sigma_{n},\mu_{n})=1$. ∎

For each $i\in\left[{k}\right]$ the number |\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}^{-1}(i)| is a binomially distributed random variable with mean $n/k$. Moreover, if \sum_{i=1}^{k}|\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}^{-1}(i)-n/k|>\eta n, then there is some $i\in\left[{k}\right]$ such that |\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}^{-1}(i)-n/k|>\eta n/k. Thus, the assertion is immediate from the Chernoff bound. ∎

Assume that there exist numbers $z>0$, $\varepsilon>0$ and a sequence $(\sigma_{n})_{n\geq 1}$ of balanced maps $\left[{n}\right]\rightarrow\left[{k}\right]$ such that

Let $\gamma=\varepsilon/(4\beta)>0$. By Lemma 6.10 there exists $\alpha>0$ such that for large enough $n$ for any set $S\subset V$ of size $|S|\leq\alpha n$ and any $\sigma:\left[{n}\right]\rightarrow\left[{k}\right]$ we have

Pick and fix a small $0<\eta<\alpha/3$ and let $\mathcal{A}$ be the event that \sum_{i=1}^{k}|\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}^{-1}(i)-n/k|\leq\eta n. Then by Lemma 6.9 there exist an ($n$-independent) number $\delta=\delta(\beta,\varepsilon,\eta)>0$ such that for $n$ large enough

Because $\sigma_{n}$ is balanced, we have $|n_{i}-n/k|\leq\sqrt{n}$ for all $i\in\left[{k}\right]$. Therefore, if $\mathcal{A}$ occurs, then it is possible to obtain from $\textstyle\sigma$ a map \tau_{\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}}\in T by changing the colors of at most $2\eta n$ vertices. If $\mathcal{A}$ occurs, we let \mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}}_{1}=G(n,p^{\prime},\tau_{\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}}). Further, let \mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}}_{2} be the random graph obtained by removing from \mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}}_{1} all edges that are monochromatic under $\textstyle\sigma$. Finally, let \mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}}_{3} be the random graph obtained from \mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}}_{2} by inserting an edge between any two vertices $v,w$ with \mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}(v)\neq\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}(w) but \tau_{\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}}(v)=\tau_{\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}}(w) with probability $p^{\prime}$ independently. Thus, the bottom line is that in \mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}}_{3}, we connect any two vertices that are colored differently under $\textstyle\sigma$ with probability $p^{\prime}$ independently. That is, \mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}}_{3}=G(n,p^{\prime},\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}).

Let S_{\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}} be the set of vertices $v$ with \mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}(v)\neq\tau_{\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}}(v) and let $\Delta$ be the number of edges we removed to obtain \mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}}_{2} from \mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}}_{1}. Then $\Delta$ is bounded by the volume of S_{\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}} in \mathchoice{\mbox{\boldmath\displaystyle G}}{\mbox{\boldmath\textstyle G}}{\mbox{\boldmath\scriptstyle G}}{\mbox{\boldmath\scriptscriptstyle G}}_{1}=G(n,p^{\prime},\tau_{\mathchoice{\mbox{\boldmath\displaystyle\sigma}}{\mbox{\boldmath\textstyle\sigma}}{\mbox{\boldmath\scriptstyle\sigma}}{\mbox{\boldmath\scriptscriptstyle\sigma}}}). Hence, (6.22) implies that

Since removing a single edge can reduce $Y$ by at most $\beta/n$, we obtain

Finally, the assertion follows from Corollary 6.3. ∎

Lemma 6.8 shows that there exist $\varepsilon>0$, balanced maps $\sigma_{n}:\left[{n}\right]\rightarrow\left[{k}\right]$ and a sequence $\mu_{n}$ satisfying $|\mu_{n}-dn/2|\leq\sqrt{n}$ such that

By the definition of $Z_{\beta,k}$, (6.25) implies that

By comparison, Lemma 6.7 yields $\beta>0$ such that with $z=\ln k+\frac{d}{2}\ln(1-1/k)+\varepsilon/8$ we have

Thus, we aim to prove that there is $\alpha>0$ such that for sufficiently large $n$

Indeed, since $\ln Z_{\beta,k}(G(n,\mu_{n},\sigma_{n}))\leq\beta\mu_{n}=O(n)$, (6.26) implies that for large enough $n$

The fixed point problem

Throughout this section we assume that $(2k-1)\ln k-3\leq d\leq(2k-1)\ln k$. Moreover, we recall that $d^{\prime}=kd/(k-1)$.

has a unique fixed point \mathchoice{\mbox{\boldmath\displaystyle q}}{\mbox{\boldmath\textstyle q}}{\mbox{\boldmath\scriptstyle q}}{\mbox{\boldmath\scriptscriptstyle q}}^{*}=(q_{1}^{*},\ldots,q_{k}^{*}) such that $\sum_{j\in\left[{k}\right]}q_{j}^{*}\geq 2/3$. This fixed point has the property that $q_{1}^{*}=\cdots=q_{k}^{*}$. Moreover, $q^{*}=kq_{1}^{*}$ is the unique fixed point of the function (4.8) in the interval $[2/3,1]$, and $q^{*}=1-O_{k}(1/k)$.

The proof of Lemma 7.1 requires several steps. We begin by studying the fixed points of $F_{d,k}$.

The function $F_{d,k}$ maps the compact set $[\frac{2}{3k},\frac{1}{k}]^{k}$ into itself and has a unique fixed point \mathchoice{\mbox{\boldmath\displaystyle q}}{\mbox{\boldmath\textstyle q}}{\mbox{\boldmath\scriptstyle q}}{\mbox{\boldmath\scriptscriptstyle q}}^{*} in this set. Moreover, the function from (4.8) has a unique fixed point $q^{*}$ in the set $[2/3,1]$ and \mathchoice{\mbox{\boldmath\displaystyle q}}{\mbox{\boldmath\textstyle q}}{\mbox{\boldmath\scriptstyle q}}{\mbox{\boldmath\scriptscriptstyle q}}^{*}=(q^{*}/k,\ldots,q^{*}/k). Furthermore,

In addition, if \mathchoice{\mbox{\boldmath\displaystyle q}}{\mbox{\boldmath\textstyle q}}{\mbox{\boldmath\scriptstyle q}}{\mbox{\boldmath\scriptscriptstyle q}}\in^{k} is a fixed point of $F_{d,k}$, then

Let $I=[\frac{2}{3k},\frac{1}{k}]^{k}$. As a first step, we show that $F_{d,k}(I)\subset I$. Indeed, let \mathchoice{\mbox{\boldmath\displaystyle q}}{\mbox{\boldmath\textstyle q}}{\mbox{\boldmath\scriptstyle q}}{\mbox{\boldmath\scriptscriptstyle q}}\in I. Then for any $i\in[k]$

On the other hand, as $d\geq(2k-1)\ln k$ we see that $d^{\prime}\geq 1.99k\ln k$. Hence,

In addition, we claim that $F_{d,k}$ is contracting on $I$. In fact, for any $i,j\in\left[{k}\right]$

Therefore, for \mathchoice{\mbox{\boldmath\displaystyle q}}{\mbox{\boldmath\textstyle q}}{\mbox{\boldmath\scriptstyle q}}{\mbox{\boldmath\scriptscriptstyle q}}\in I the Jacobi matrix DF_{d,k}(\mathchoice{\mbox{\boldmath\displaystyle q}}{\mbox{\boldmath\textstyle q}}{\mbox{\boldmath\scriptstyle q}}{\mbox{\boldmath\scriptscriptstyle q}}) satisfies

Thus, $F_{d,k}$ is a contraction on the compact set $I$. Consequently, Banach’s fixed point theorem implies that there is a unique fixed point \mathchoice{\mbox{\boldmath\displaystyle q}}{\mbox{\boldmath\textstyle q}}{\mbox{\boldmath\scriptstyle q}}{\mbox{\boldmath\scriptscriptstyle q}}_{*}\in I.

To establish (7.3), assume without loss that \mathchoice{\mbox{\boldmath\displaystyle q}}{\mbox{\boldmath\textstyle q}}{\mbox{\boldmath\scriptstyle q}}{\mbox{\boldmath\scriptscriptstyle q}}=(q_{1},\ldots,q_{k})\in^{k} is a fixed point such that $q_{1}\leq\cdots\leq q_{k}$. Then $q_{1}>0$ because $F_{d,k}$ maps $^{k}$ into $(0,1]^{k}$. Moreover, because $\textstyle q$ is a fixed point, we find

Further, we claim that the function $f_{d,k}:\rightarrow$, $q\mapsto(1-\exp(-dq/(k-1)))^{k-1}$ maps the interval $[2/3,1]$ into itself. This is because for $q\in[2/3,1]$ we have $0\leq\exp(-dq/(k-1))\leq k^{-1.3}$ due to our assumption on $d$. Moreover, the derivative of $f$ works out to be $f^{\prime}_{d,k}(q)=d\exp(-dq/(k-1))(1-\exp(-dq/(k-1)))^{k-2}$. Thus, for $q\in[2/3,1]$ we find $0\leq f^{\prime}_{d,k}(q)<1/2$. Hence, $f_{d,k}$ has a unique fixed point $q_{*}\in[2/3,1]$. Comparing the expressions $f_{d,k}(q)$ and F_{d,k}(\mathchoice{\mbox{\boldmath\displaystyle q}}{\mbox{\boldmath\textstyle q}}{\mbox{\boldmath\scriptstyle q}}{\mbox{\boldmath\scriptscriptstyle q}}), we see that $(q_{*}/k,\ldots,q_{*}/k)$ is a fixed point of $F_{d,k}$. Consequently, \mathchoice{\mbox{\boldmath\displaystyle q}}{\mbox{\boldmath\textstyle q}}{\mbox{\boldmath\scriptstyle q}}{\mbox{\boldmath\scriptscriptstyle q}}_{*}=(q_{*}/k,\ldots,q_{*}/k).

Finally, since $f^{\prime}_{d,k}(q)>0$ for all $q$, the function $f_{d,k}$ is strictly increasing. Therefore, as $d=(2-o_{k}(1))k\ln k$,

Similarly, $q_{*}\geq f_{d,k}(2/3)\geq 1-k^{-0.3}$. Hence, because $d\geq(2k-1)\ln k-3$, we obtain

Combining (7.4) and (7.5), we conclude that $q_{*}=1-1/k+o_{k}(1/k)$, as claimed. ∎

From here on out, we let \mathchoice{\mbox{\boldmath\displaystyle q}}{\mbox{\boldmath\textstyle q}}{\mbox{\boldmath\scriptstyle q}}{\mbox{\boldmath\scriptscriptstyle q}}^{*} denote the fixed point of $F_{d,k}$ in $[2/(3k),1]^{k}$ and we denote the fixed point of the function (4.8) in the interval $[2/3,1]$ by $q^{*}$. Hence, \mathchoice{\mbox{\boldmath\displaystyle q}}{\mbox{\boldmath\textstyle q}}{\mbox{\boldmath\scriptstyle q}}{\mbox{\boldmath\scriptscriptstyle q}}^{*}=(q^{*}/k,\ldots,q^{*}/k). If we keep $k$ fixed, how does $q^{*}$ vary with $d$?

The map $d\mapsto q^{*}$ is differentiable by the implicit function theorem. Moreover, differentiating (4.8) while keeping in mind that $q^{*}=q^{*}(d)$ is a fixed point, we find

Rearranging the above using $d=2k\ln k+O_{k}(\ln k)$ and (7.2) yields the assertion. ∎

Lemma 7.2 shows that $q_{j}^{*}=q_{*}/k$ for all $j\in\left[{k}\right]$. Hence, due to (7.2) and because $d^{\prime}=2k\ln k+O_{k}(\ln k)$ we obtain

Furthermore, applying Corollary 7.4, we get

Fix a number $d\in[(2k-1)\ln k-2,(2k-1)\ln k]$ and a small number $\varepsilon>0$ and let $\hat{d}=d+\varepsilon$. Let \mathchoice{\mbox{\boldmath\displaystyle q}}{\mbox{\boldmath\textstyle q}}{\mbox{\boldmath\scriptstyle q}}{\mbox{\boldmath\scriptscriptstyle q}}^{*} be the unique fixed point of $F_{d,k}$ in $[2/3,1]^{k}$ and let \mathchoice{\mbox{\boldmath\displaystyle\hat{q}}}{\mbox{\boldmath\textstyle\hat{q}}}{\mbox{\boldmath\scriptstyle\hat{q}}}{\mbox{\boldmath\scriptscriptstyle\hat{q}}}^{*} be the unique fixed point of $F_{\hat{d},k}$ in $[2/3,1]^{k}$. Set $d^{\prime}=dk/(k-1)$ and $\hat{d}^{\prime}=\hat{d}k/(k-1)$. Moreover, let us introduce the shorthands \mathchoice{\mbox{\boldmath\displaystyle T}}{\mbox{\boldmath\textstyle T}}{\mbox{\boldmath\scriptstyle T}}{\mbox{\boldmath\scriptscriptstyle T}}=\mathchoice{\mbox{\boldmath\displaystyle T}}{\mbox{\boldmath\textstyle T}}{\mbox{\boldmath\scriptstyle T}}{\mbox{\boldmath\scriptscriptstyle T}}_{d,k,\mathchoice{\mbox{\boldmath\displaystyle q}}{\mbox{\boldmath\textstyle q}}{\mbox{\boldmath\scriptstyle q}}{\mbox{\boldmath\scriptscriptstyle q}}^{*}} and \hat{\mathchoice{\mbox{\boldmath\displaystyle T}}{\mbox{\boldmath\textstyle T}}{\mbox{\boldmath\scriptstyle T}}{\mbox{\boldmath\scriptscriptstyle T}}}=\mathchoice{\mbox{\boldmath\displaystyle T}}{\mbox{\boldmath\textstyle T}}{\mbox{\boldmath\scriptstyle T}}{\mbox{\boldmath\scriptscriptstyle T}}_{d,k,\mathchoice{\mbox{\boldmath\displaystyle\hat{q}}}{\mbox{\boldmath\textstyle\hat{q}}}{\mbox{\boldmath\scriptstyle\hat{q}}}{\mbox{\boldmath\scriptscriptstyle\hat{q}}}^{*}}. We aim to bound

To this end, we couple $\textstyle T$ and \hat{\mathchoice{\mbox{\boldmath\displaystyle T}}{\mbox{\boldmath\textstyle T}}{\mbox{\boldmath\scriptstyle T}}{\mbox{\boldmath\scriptscriptstyle T}}} as follows.

Given that the total progeny is finite, we obtain \widetilde{\mathchoice{\mbox{\boldmath\displaystyle T}}{\mbox{\boldmath\textstyle T}}{\mbox{\boldmath\scriptstyle T}}{\mbox{\boldmath\scriptscriptstyle T}}} by linking each individual to its offspring.

Further, since |\mathchoice{\mbox{\boldmath\displaystyle T}}{\mbox{\boldmath\textstyle T}}{\mbox{\boldmath\scriptstyle T}}{\mbox{\boldmath\scriptscriptstyle T}}|^{-1}\ln\mathcal{Z}(\mathchoice{\mbox{\boldmath\displaystyle T}}{\mbox{\boldmath\textstyle T}}{\mbox{\boldmath\scriptstyle T}}{\mbox{\boldmath\scriptscriptstyle T}}),|\hat{\mathchoice{\mbox{\boldmath\displaystyle T}}{\mbox{\boldmath\textstyle T}}{\mbox{\boldmath\scriptstyle T}}{\mbox{\boldmath\scriptscriptstyle T}}}|^{-1}\ln\mathcal{Z}(\hat{\mathchoice{\mbox{\boldmath\displaystyle T}}{\mbox{\boldmath\textstyle T}}{\mbox{\boldmath\scriptstyle T}}{\mbox{\boldmath\scriptscriptstyle T}}})\leq\ln k with certainty, we obtain

Combining (7.6) and (7.7), we conclude that

The first assertion is immediate from Lemma 7.2. The second claim follows from Lemma 7.6, and the third one from Lemma 7.7. ∎

2. The “hard fields”

Further, for a real $\lambda\geq 0$ and an integer $y\geq 1$ we let

Moreover, for $i\in\left[{k}\right]$ we let $\Gamma_{i}$ be the set of all non-negative integer vectors \mathchoice{\mbox{\boldmath\displaystyle\gamma}}{\mbox{\boldmath\textstyle\gamma}}{\mbox{\boldmath\scriptstyle\gamma}}{\mbox{\boldmath\scriptscriptstyle\gamma}}=(\gamma_{j})_{j\in\left[{k}\right]\setminus\left\{{i}\right\}} and for \mathchoice{\mbox{\boldmath\displaystyle\gamma}}{\mbox{\boldmath\textstyle\gamma}}{\mbox{\boldmath\scriptstyle\gamma}}{\mbox{\boldmath\scriptscriptstyle\gamma}}\in\Gamma_{i} we set

We also let \Omega^{\mathchoice{\mbox{\boldmath\displaystyle\gamma}}{\mbox{\boldmath\textstyle\gamma}}{\mbox{\boldmath\scriptstyle\gamma}}{\mbox{\boldmath\scriptscriptstyle\gamma}}}=\prod_{h\in[k]\setminus\{i\}}\prod_{j\in[\gamma_{h}]}\Omega for \mathchoice{\mbox{\boldmath\displaystyle\gamma}}{\mbox{\boldmath\textstyle\gamma}}{\mbox{\boldmath\scriptstyle\gamma}}{\mbox{\boldmath\scriptscriptstyle\gamma}}\in\Gamma_{i}. The elements of \Omega^{\mathchoice{\mbox{\boldmath\displaystyle\gamma}}{\mbox{\boldmath\textstyle\gamma}}{\mbox{\boldmath\scriptstyle\gamma}}{\mbox{\boldmath\scriptscriptstyle\gamma}}} are denoted by \mu_{\mathchoice{\mbox{\boldmath\displaystyle\gamma}}{\mbox{\boldmath\textstyle\gamma}}{\mbox{\boldmath\scriptstyle\gamma}}{\mbox{\boldmath\scriptscriptstyle\gamma}}}=(\mu_{h,j})_{h\in[k]\setminus\{i\},j\in[\gamma_{h}]}. Moreover, let

Thus, with the convention from the previous paragraph, in the case \mathchoice{\mbox{\boldmath\displaystyle\gamma}}{\mbox{\boldmath\textstyle\gamma}}{\mbox{\boldmath\scriptstyle\gamma}}{\mbox{\boldmath\scriptscriptstyle\gamma}}=0 the set \Omega^{\mathchoice{\mbox{\boldmath\displaystyle\gamma}}{\mbox{\boldmath\textstyle\gamma}}{\mbox{\boldmath\scriptstyle\gamma}}{\mbox{\boldmath\scriptscriptstyle\gamma}}}=\left\{{\emptyset}\right\} contains only one element, namely $\mu_{0}=\emptyset$. Moreover, \pi_{i,\mathchoice{\mbox{\boldmath\displaystyle\gamma}}{\mbox{\boldmath\textstyle\gamma}}{\mbox{\boldmath\scriptstyle\gamma}}{\mbox{\boldmath\scriptscriptstyle\gamma}}} is the probability measure on $\Omega^{0}$ that gives mass one to the point $\emptyset$. We recall the map $\mathcal{B}:\bigcup_{\gamma\geq 1}\Omega^{\gamma}\rightarrow\Omega$ from (2.1) and extend this map to $\Omega^{0}$ by letting \mathcal{B}(\emptyset)=\frac{1}{k}\mathchoice{\mbox{\boldmath\displaystyle 1}}{\mbox{\boldmath\textstyle 1}}{\mbox{\boldmath\scriptstyle 1}}{\mbox{\boldmath\scriptscriptstyle 1}} be the uniform distribution on $\Omega$. We start the proof of Lemma 7.8 by establishing the following identity.

If $\pi$ is fixed point of $\mathcal{F}_{d,k}$, then for any $i\in\left[{k}\right]$ we have

To establish Lemma 7.9 we need to calculate the normalising quantities $Z_{\gamma}(\pi)$.

If $\pi$ is fixed point of $\mathcal{F}_{d,k}$, then $Z_{\gamma}(\pi)=(k-1)^{\gamma}/k^{\gamma-1}$.

Assume that $\pi$ is fixed point of $\mathcal{F}_{d,k}$. We claim that

Now, assume that $h_{1},h_{2}\in\left[{k}\right]$ are such that $\nu(h_{1})\leq\nu(h_{2})$. Then (7.15) yields

Hence, $\nu(h_{1})=\nu(h_{2})$ for all $h_{1},h_{2}\in\left[{k}\right]$, which implies (7.14). Finally, the assertion follows from (7.14) and the definition (2.2) of $Z_{\gamma}(\pi)$. ∎

If $\pi$ is a fixed point of $\mathcal{F}_{d,k}$, then by Lemma 7.10 and the definition (2.1) of the map $\mathcal{B}$ we have

Further, for any $\mu\in\Omega$ we have $1-\mu(i)=\sum_{i^{\prime}\neq i}\mu(i^{\prime})$. Hence,

In the last expression, we can think of generating the sequence $i_{1},\ldots,i_{\gamma}$ as follows: first, choose $\gamma$ from the Poisson distribution ${\rm Po}(d)$. Then, choose the sequence $i_{1},\ldots,i_{\gamma}$ by independently choosing $i_{j}$ from the set $\left[{k}\right]\setminus\left\{{i}\right\}$ uniformly at random. Thus, in the overall experiment the number of times that each color $h$ occurs has distribution ${\rm Po}(d/(k-1))$, independently for all $h\in\left[{k}\right]\setminus\left\{{i}\right\}$, whence (7.16) implies the assertion. ∎

If $\pi$ is fixed point of $\mathcal{F}_{d}$, then $(\rho_{i}(\pi))_{i\in\left[{k}\right]}$ is a fixed point of the function $F_{d,k}$ from Lemma 7.1.

Invoking Lemma 7.9, we obtain for any $i\in\left[{k}\right]$

A glimpse at the definition (2.1) of $\mathcal{B}$ reveals that \delta_{i}=\mathcal{B}[\mu_{\mathchoice{\mbox{\boldmath\displaystyle\gamma}}{\mbox{\boldmath\textstyle\gamma}}{\mbox{\boldmath\scriptstyle\gamma}}{\mbox{\boldmath\scriptscriptstyle\gamma}}}] iff for each $h\in\left[{k}\right]\setminus\left\{{i}\right\}$ there is $j\in\left[{\gamma_{h}}\right]$ such that $\mu_{h,j}=\delta_{h}$. Further, in (7.17) the $\mu_{h,j}$ are chosen independently from the distribution $\pi_{h}$, and $\pi_{h}(\left\{{\delta_{h}}\right\})=k\rho_{h}(\pi)$. In effect, the r.h.s. of (7.17) is simply the probability that if we choose numbers $\gamma_{h}$ independently from the Poisson distribution with mean $d/(k-1)$ for $h\neq i$ and then perform $\gamma_{h}$ independent Bernoulli experiments with success probability $k\rho_{h}(\pi)$, then there occurs at least one success for each $h\neq i$. Of course, this is nothing but the probability that $k-1$ independent Poisson variables $({\rm Po}(\rho_{h}(\pi)dk/(k-1)))_{h\neq i}$ are all strictly positive. Hence,

Consequently, $(\rho_{i}(\pi))_{i\in\left[{k}\right]}=F_{d,k}((\rho_{i}(\pi))_{i\in\left[{k}\right]})$. ∎

Assume that $\pi\in\mathcal{P}$ is a frozen fixed point of $\mathcal{F}_{d,k}$. Then $\rho_{i}(\pi)\geq\frac{2}{3k}$ for all $i\in\left[{k}\right]$. Hence, Corollary 7.11 shows that $(\rho_{1}(\pi),\ldots,\rho_{k}(\pi))\in[\frac{2}{3k},1]$ is a fixed point of $F_{d,k}$. Therefore, Lemma 7.1 implies that $\rho_{i}(\pi)=q^{*}/k$ for all $i\in\left[{k}\right]$.

Given $\textstyle\gamma$, the distributions $\mu_{h,j}$ are chosen independently from $\pi_{h}$ for all $h\neq i$, $j\in\left[{\gamma_{h}}\right]$. Hence, for a given $\textstyle\gamma$ the probability that (1) and (2) occur is precisely

Thus, combining (7.18) and (7.19), we see that

3. The fixed point

The objective in this section is to establish

Suppose that $d\geq(2k-1)\ln k-2$. Then \pi_{d,k,\mathchoice{\mbox{\boldmath\displaystyle q}}{\mbox{\boldmath\textstyle q}}{\mbox{\boldmath\scriptstyle q}}{\mbox{\boldmath\scriptscriptstyle q}}^{*}} is the unique frozen fixed point of $\mathcal{F}_{d,k}$.

Let $\mathcal{X}$ be the set of all frozen fixed points of $\mathcal{F}_{d,k}$. Moreover, let $\widetilde{\mathcal{X}}$ be the set of all fixed points of

Thus, if $\pi$ is a frozen fixed point of $\mathcal{F}_{d,k}$, then $\widetilde{\pi}$ is a fixed point of $\widetilde{\mathcal{F}}_{d,k}$.