Phase transitions in the coloring of random graphs

We consider the problem of coloring the vertices of a large sparse random graph with a given number of colors so that no adjacent vertices have the same color. Using the cavity method, we present a detailed and systematic analytical study of the space of proper colorings (solutions). We show that for a fixed number of colors and as the average vertex degree (number of constraints) increases, the set of solutions undergoes several phase transitions similar to those observed in the mean field theory of glasses. First, at the clustering transition, the entropically dominant part of the phase space decomposes into an exponential number of pure states so that beyond this transition a uniform sampling of solutions becomes hard. Afterward, the space of solutions condenses over a finite number of the largest states and consequently the total entropy of solutions becomes smaller than the annealed one. Another transition takes place when in all the entropically dominant states a finite fraction of nodes freezes so that each of these nodes is allowed a single color in all the solutions inside the state. Eventually, above the coloring threshold, no more solutions are available. We compute all the critical connectivities for Erdős-Rényi and regular random graphs and determine their asymptotic values for a large number of colors. Finally, we discuss the algorithmic consequences of our findings. We argue that the onset of computational hardness is not associated with the clustering transition and we suggest instead that the freezing transition might be the relevant phenomenon. We also discuss the performance of a simple local Walk-COL algorithm and of the belief propagation algorithm in the light of our results.

Figure 1

A sketch of the set of solutions when the average connectivity (degree) is increased. At low connectivities (on the left), all solutions are in a single cluster. For larger $c$, clusters of solutions appear but the single giant cluster still exists and dominates the measure. At the dynamic/clustering transition $c_d$, the phase space slits in an exponential number of clusters. At the condensation/Kauzmann transition $c_c$, the measure condenses over the largest of them. Finally, no solutions exist above the COL/UNCOL transition $c_s$. The rigidity/freezing transition $c_r$ (which might appear before or after the condensation transition) takes place when the dominating clusters (the minimal set of clusters that covers almost all proper colorings) start to contain frozen variables. The clusters containing frozen variables are colored in black and those which do not are colored in gray.

Figure 2

Iterative construction of a tree by adding a new Potts spin.

Figure 3

The lines are solutions of Eq. (40) and give the total fraction $q\eta$ of hard fields for a given value of ratio $r=\overline{Z_{\mathrm{soft}}^m}∕\overline{Z_{\mathrm{hard}}^m}$ for $q=3$ (a) and $q=4$ (b) in regular random graphs. There is a critical value of the ratio (full point) beyond which only the trivial solution $\eta =0$ exists. Note that the solutions at $m=0$ and $m=1$ only exist for a connectivity large enough.

Figure 4

Complexity as a function of the internal state entropy for the $q$-coloring problem on random regular graphs of connectivity $c$. The full line corresponds to the clusters where a finite fraction of hard fields (frozen variables) is present and the dotted line to the clusters without hard fields. The circle signs the entropically dominating clusters. (a) ($q=4$, $c=9$) is in the clustered phase; ($q=5$, $c=13$) is in a simple replica symmetric phase; and ($q=5$, $c=14$) is in the condensed clustered phase. (b) Results for six-coloring for connectivities 17 (RS), 18 (clustered), 19 (condensed), and 20 (uncolorable). For 4-, 5-, and six-coloring all the smaller connectivities are in the RS phase while all the larger one are uncolorable.

Figure 5

The complexity as a function of entropy for four-coloring of biregular graphs. (a) 5-21-biregular graph, an example where the entropy is dominated by clusters with soft fields while the gap in the curve $\Sigma \left(s\right)$ still exists. (b) 4-$c$-biregular graphs for $c=36,39,42,45$. In all these cases the replica symmetric solution is locally unstable. In the dependence $\Sigma \left(s\right)$ we see an unphysical branch of the complexity, which is zoomed in the inset for $c=39$.

Figure 6

The 1RSB total entropy and complexity of the dominating clusters for four- and five-coloring of Erdős-Rényi random graphs. The complexity jumps discontinuously at the clustering transition $c_d$ while the total entropy stays analytical. The complexity disappears at the condensation transition $c_c$ causing a nonanalyticity in the total entropy. Finally, the total entropy discontinuously disappears at the coloring threshold. Dashed is the RS entropy left for comparison.

Figure 7

Left: The total entropy for three-coloring of Erdős-Rényi random graphs. The dashed line is the replica symmetric (also the annealed) entropy, left for comparison. The complexity at $m=1$ is shown; it is negative for $c>4$, however, for connectivity near to four it is very near to zero. Right: The values of parameter $m^{*}$, $\Sigma \left(m^{*}\right)=0$, as a function of connectivity for $q=3,4,5$ and in the large $q$ limit. The connectivity $c$ is rescaled as $(c-c_c)∕(c_s-c_c)$. It is striking that for $q>3$ the curves are so well fitted by the large $q$ limit one. We are even not able to see the difference due to the error bars which are roughly of the point size.

Figure 8

(a) Overlaps structure in three-coloring of random graphs as a function of connectivity. The intracluster overlap (upper curve) grows continuously from 1/3 at the clustering transition $c=4$. In the figure from up there are $\delta ={\delta }_3$, ${\delta }_1$, and ${\delta }_0$. (b) Overlaps structure in four-coloring of random graphs as a function of connectivity. The intracluster overlap (upper curve) jumps discontinuously from 1/4 at the clustering transition $c=8.35$. The probability that two random solutions belong to the same cluster, however, is zero between the clustering and condensation transition $[8.35,8.46]$. In the figure from up there are $\delta ={\delta }_4$, ${\delta }_2$, ${\delta }_1$, and ${\delta }_0$.

Figure 9

Analytical result for the large $q$ asymptotics close to the COL/UNCOL transition for $c=2q\ln q-\ln q+\alpha$. Left: (rescaled) complexity versus (rescaled) internal entropy for different connectivities. The condensation transition appears for $\alpha =-2\ln 2$. The maximum of the complexity becomes zero at $c_s$ for $\alpha =-1$. Right: Total entropy $\left(s^{\mathrm{tot}}\right)$, complexity $\left({\Sigma }^{*}\right)$, and the parameter $m^{*}$ versus $\alpha$. Notice how the values for the total number of solutions are already very close to those for finite low $q$ in Figs. 6, 7.

Figure 10

Performance of the Walk-COL algorithm in coloring random graphs for three-coloring (a) and four-coloring (b). We plot the rescaled time (averaged over five instances) needed to color a graph of connectivity $c$. The strategy allows one to go beyond the clustering transition ($c_d=4$ for three-coloring and $c_d=8.35$ for four-coloring) in linear time with respect to the size of the graph.

Figure 11

Performance of the BP algorithm plus decimation in coloring random graphs for three-coloring (a) and four-coloring (b). The strategy described in the text allows one to color random graphs beyond the clustering and even the condensation transitions.

Figure 12

The sketch of size of the largest clusters for a given value of parameter $m^{*}$. The lower curve is related to the average size of the largest clusters as $1∕\mathbb{E}[1∕x_1]=1-m^{*}$. The following curves are related to the size of $i$ largest clusters, their distances are $\mathbb{E}\left[R_i\right]\mathbb{E}\left[R_{i-1}\right]\cdots \mathbb{E}\left[R_1\right](1-m^{*})$.

Figure 13

Histograms of the first component of the cavity field ${\psi }_1$, i.e., the probability that a node takes color one. Notice the logarithmic $y$ scale. Frozen fields $({\psi }_1=1)$ are present in the solution for the three upper cases; there are delta peaks on 0, 1, 1/2, and other simple fractions depending on $q$. Notice that even when frozen fields are not present, there are many almost frozen fields (the distributions only concentrate around $0$, $1$, $1∕2$, and other fractions).

Figure 14

Fraction of the hard and the quasihard cavity fields $q\eta$ (a field is quasihard if $\psi >1-ϵ$) in the four-coloring of nine-regular graphs. The bold line is obtained with the analytical computation of the fraction of hard fields and the dot corresponds to the threshold $m_r$.

Figure 15

The numerical results for the free entropy (30) and its fit with a function $a+b{2}^x+c{3}^x+\cdots$ for the six-coloring of 19-regular graphs and the four-coloring of nine-regular graphs. Circles give the analytical results at $m=0$ and $m=1$. On the right parts, we present the complexity versus internal entropy with the numerical points and the Legendre transform of the fit of the free entropy. The analytical result for ${\Sigma }_{\max }$ is also shown.