Phase Transitions in the Coloring of Random Graphs

By Lenka Zdeborov'a, Florent Krzakala. 2007

227 citations recorded by the source corpus.

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 Erdos-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.

Subfields: Computational Theory and Mathematics, Condensed Matter Physics, Statistical and Nonlinear Physics, Algorithms & Complexity, AI for Physical Sciences

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Condensed Matter Physics

In Statistical and Nonlinear Physics

In Algorithms & Complexity

In AI for Physical Sciences

Citations in the corpus

The jamming transition as a paradigm to understand the loss landscape of deep neural networks (2018, background): “[32] Lenka Zdeborová and Florent Krzakala, “Phase transitions in the coloring of random graphs,” Physical Review E 76, 031131 (2007).”
A jamming transition from under- to over-parametrization affects loss landscape and generalization (2018, background): “In the last decade physicists have unveiled an analogy between the physical phenomenon of jamming [17, 18], which characterizes the onset of rigidity in disordered packings of particles, and phase transitions taking place in certain classes of computational optimization and learning problems [19, 20”
A Landscape Analysis of Constraint Satisfaction Problems (2007, methodology): “In practice, for the readjustment of the trees with root A or B, we use a Walk-COL algorithm introduced in [30], which is the coloring version of the celebrated Walk-SAT program [21, 40] This is perhaps not ideal, but it definitely provides an upper bound of the number of flips needed.”
Statistical physics of inference: thresholds and algorithms (2015, background): “In the large q limit the dynamical and detectability phase transitions can be deduced from [235] while keeping in mind the concept of quiet planting”
Mean-field theory of hard sphere glasses and jamming (2008, background): “It has been called freezing or rigidity transition and is characterized by the appearance of a finite fraction of frozen particles in the system (Semerjian, 2008; Zdeborová and Krzakala, 2007).”