The DOI matches its Crossref record; 72 of the 72 references it cites were found in a registry or an index.
Phase transitions in the coloring of random graphs
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
(1988) · Cited by 16,582
Bollobás, B. (1985) · Cited by 6,196
Proceedings of the 19th International Joint Conference on Artificial Intelligence
Pujol, J. M., Delgado, J., Ramon Sangüesa, A., & Flache, A. (2005) · International Joint Conference on Artificial Intelligence · Cited by 5,771
Erdős, P., & Rényi, A. (2022) · Publicationes Mathematicae Debrecen · doi:10.5486/pmd.1959.6.3-4.12 · Cited by 5,337
Electric Moments of Molecules in Liquids
Onsager, L. (1936) · Journal of the American Chemical Society · doi:10.1021/ja01299a050 · Cited by 5,329
Non-Uniform Random Variate Generation
Devroye, L. (1986) · Springer eBooks · doi:10.1007/978-1-4613-8643-8 · Cited by 4,041
Spin Glass Theory and Beyond: An Introduction to the Replica Method and Its Applications
Mezard, M., Parisi, G., & Virasoro, M. (1986) · World Scientific Lecture Notes in Physics · doi:10.1142/0271 · Cited by 3,653
Wu, F. Y. (1982) · Reviews of Modern Physics · doi:10.1103/revmodphys.54.235 · Cited by 3,570
The Nature of the Glassy State and the Behavior of Liquids at Low Temperatures.
Kauzmann, W. (1948) · Chemical Reviews · doi:10.1021/cr60135a002 · Cited by 2,834
Complexity of Computer Computations
(1972) · Springer eBooks · doi:10.1007/978-1-4684-2001-2 · Cited by 2,781
Mezard, M., Parisi, G., Virasoro, M. A., & Thouless, D. J. (1988) · Physics Today · doi:10.1063/1.2811676 · Cited by 2,682
Bollobás, B. (2001) · doi:10.1017/cbo9780511814068 · Cited by 2,639
Łuczak, T., Janson, S., & Ruciński, A. (2000) · Cited by 2,192
Proceedings of the 56th Annual ACM Symposium on Theory of Computing
(2024) · doi:10.1145/3618260 · Cited by 1,730
Jamming at zero temperature and zero applied stress: The epitome of disorder
O’Hern, C. S., Silbert, L. E., Liu, A. J., & Nagel, S. R. (2003) · Physical Review E · doi:10.1103/physreve.68.011306 · Cited by 1,599
Janson, S., Łuczak, T., & Rucinski, A. (2000) · Wiley eBooks · doi:10.1002/9781118032718 · Cited by 1,545
Gibbs Measures and Phase Transitions
Georgii, H.-O. (2011) · De Gruyter eBooks · doi:10.1515/9783110250329 · Cited by 1,374
Random-energy model: An exactly solvable model of disordered systems
Derrida, B. (1981) · Physical Review B · doi:10.1103/physrevb.24.2613 · Cited by 1,350
The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator
Pitman, J., & Yor, M. (1997) · The Annals of Probability · doi:10.1214/aop/1024404422 · Cited by 1,202
Analytic and Algorithmic Solution of Random Satisfiability Problems
Mézard, M., Parisi, G., & Zecchina, R. (2002) · Science · doi:10.1126/science.1073287 · Cited by 1,071
Statistical theory of superlattices
Bethe, H. A. (1935) · Proceedings of the Royal Society of London. Series A - Mathematical and Physical Sciences · doi:10.1098/rspa.1935.0122 · Cited by 1,069
Scaling concepts for the dynamics of viscous liquids near an ideal glassy state
Kirkpatrick, T. R., Thirumalai, D., & Wolynes, P. G. (1989) · Physical Review A · doi:10.1103/physreva.40.1045 · Cited by 1,038
A sequence of approximated solutions to the S-K model for spin glasses
Parisi, G. (1980) · Journal of Physics A: Mathematical and General · doi:10.1088/0305-4470/13/4/009 · Cited by 821
The Bethe lattice spin glass revisited
Mézard, M., & Parisi, G. (2001) · The European Physical Journal B · doi:10.1007/pl00011099 · Cited by 818
Random-Energy Model: Limit of a Family of Disordered Models
Derrida, B. (1980) · Physical Review Letters · doi:10.1103/physrevlett.45.79 · Cited by 811
Determining computational complexity from characteristic ‘phase transitions’
Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., & Troyansky, L. (1999) · Nature · doi:10.1038/22055 · Cited by 790
Statistical Theory of Superlattices
Bethe, H. A. (1997) · World Scientific Series in 20th Century Physics · doi:10.1142/9789812795755_0010 · Cited by 740
Every planar map is four colorable. Part II: Reducibility
Appel, K., Haken, W., & Koch, J. (1977) · Illinois Journal of Mathematics · doi:10.1215/ijm/1256049012 · Cited by 704
Gibbs states and the set of solutions of random constraint satisfaction problems
Krz̧akała, F., Montanari, A., Ricci-Tersenghi, F., Semerjian, G., & Zdeborová, L. (2007) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0703685104 · Cited by 546
Self-citationExploring artificial intelligence in the new millennium
Lakemeyer, G. (2003) · Cited by 480
Structural Glass Transition and the Entropy of the Metastable States
Monasson, R. (1995) · Physical Review Letters · doi:10.1103/physrevlett.75.2847 · Cited by 456
RandomK-satisfiability problem: From an analytic solution to an efficient algorithm
Mézard, M., & Zecchina, R. (2002) · Physical Review E · doi:10.1103/physreve.66.056126 · Cited by 448
Sudden Emergence of a Giantk-Core in a Random Graph
Pittel, B., Spencer, J., & Wormald, N. (1996) · Journal of Combinatorial Theory, Series B · doi:10.1006/jctb.1996.0036 · Cited by 437
Survey propagation: An algorithm for satisfiability
Braunstein, A., Mézard, M., & Zecchina, R. (2005) · Random Structures & Algorithms · doi:10.1002/rsa.20057 · Cited by 433
Spin Glasses: A Challenge for Mathematicians
Talagrand, M. (2003) · Cited by 402
Dynamics of the Structural Glass Transition and thep-Spin—Interaction Spin-Glass Model
Kirkpatrick, T. R., & Thirumalai, D. (1987) · Physical Review Letters · doi:10.1103/physrevlett.58.2091 · Cited by 392
Mean-field theory of the Potts glass
Gross, D. J., Kanter, I., & Sompolinsky, H. (1985) · Physical Review Letters · doi:10.1103/physrevlett.55.304 · Cited by 377
The Cavity Method at Zero Temperature
Mézard, M., & Parisi, G. (2003) · Journal of Statistical Physics · doi:10.1023/a:1022221005097 · Cited by 367
Thermodynamics of Glasses: A First Principles Computation
Mézard, M., & Giorgio Parisi, A. (1999) · Physical Review Letters · doi:10.1103/physrevlett.82.747 · Cited by 330
Generating hard satisfiability problems
Selman, B., Mitchell, D. G., & Levesque, H. J. (1996) · Artificial Intelligence · doi:10.1016/0004-3702(95)00045-3 · Cited by 296
Rigorous location of phase transitions in hard optimization problems
Achlioptas, D., Naor, A., & Peres, Y. (2005) · Nature · doi:10.1038/nature03602 · Cited by 279
The ζ(2) limit in the random assignment problem
Aldous, D. J. (2001) · Random Structures & Algorithms · doi:10.1002/rsa.1015 · Cited by 278
ACM-SIAM Symposium on Discrete Algorithms
Clifford, R., Jalsenius, M., & Sach, B. (2015) · Symposium on Discrete Algorithms · Cited by 273
Phase transitions and the search problem
Hogg, T., Huberman, B. A., & Williams, C. P. (1996) · Artificial Intelligence · doi:10.1016/0004-3702(95)00044-5 · Cited by 249
Rigorous Inequalities Between Length and Time Scales in Glassy Systems
Montanari, A., & Semerjian, G. (2006) · Journal of Statistical Physics · doi:10.1007/s10955-006-9175-y · Cited by 244
The Application of the Bethe-Peierls Method to Ferromagnetism
Weiss, P. R. (1948) · Physical Review · doi:10.1103/physrev.74.1493 · Cited by 223
Clustering of Solutions in the Random Satisfiability Problem
Mézard, M., Mora, T., & Zecchina, R. (2005) · Physical Review Letters · doi:10.1103/physrevlett.94.197205 · Cited by 207
Mulet, R., Pagnani, A., Weigt, M., & Zecchina, R. (2002) · Physical Review Letters · doi:10.1103/physrevlett.89.268701 · Cited by 191
The chromatic number of random graphs
Łuczak, T. (1991) · Combinatorica · doi:10.1007/bf01375472 · Cited by 185
Algorithmic theory of random graphs
FRIEZE, A. M., & McDiarmid, C. (1997) · Random Structures and Algorithms · doi:10.1002/(sici)1098-2418(199701/03)10:1/2<5::aid-rsa2>3.0.co;2-z · Cited by 185
On the nature of the low-temperature phase in discontinuous mean-field spin glasses
Andrea Montanari, A., & Ricci‐Tersenghi, F. (2003) · The European Physical Journal B · doi:10.1140/epjb/e2003-00174-7 · Cited by 168
Landscape analysis of constraint satisfaction problems
Krzakala, F., & Kurchan, J. (2007) · Physical Review E · doi:10.1103/physreve.76.021122 · Cited by 162
Glass models on Bethe lattices
Rivoire, O., Biroli, G., Martin, O., & M�zard, M. (2003) · The European Physical Journal B · doi:10.1140/epjb/e2004-00030-4 · Cited by 142
Extremal optimization for graph partitioning
Boettcher, S., & Percus, A. G. (2001) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.64.026114 · Cited by 138
Survey propagation as local equilibrium equations
Braunstein, A., & Zecchina, R. (2004) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2004/06/p06007 · Cited by 137
Instability of one-step replica-symmetry-broken phase in satisfiability problems
Andrea Montanari, A., Giorgio Parisi, A., & Ricci‐Tersenghi, F. (2004) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/37/6/008 · Cited by 130
A ferromagnet with a glass transition
Franz, S., Mézard, M., Ricci‐Tersenghi, F., Weigt, M., & Zecchina, R. (2001) · Europhysics Letters (EPL) · doi:10.1209/epl/i2001-00438-4 · Cited by 129
Critical behavior in the computational cost of satisfiability testing
Selman, B., & Kirkpatrick, S. (1996) · Artificial Intelligence · doi:10.1016/0004-3702(95)00056-9 · Cited by 129
Exploiting the deep structure of constraint problems
Williams, C. P., & Hogg, T. (1994) · Artificial Intelligence · doi:10.1016/0004-3702(94)90104-x · Cited by 120
Polynomial iterative algorithms for coloring and analyzing random graphs
Braunstein, A., Mulet, R., Pagnani, A., Weigt, M., & Zecchina, R. (2003) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.68.036702 · Cited by 111
On the Dynamics of the Glass Transition on Bethe Lattices
Andrea Montanari, A., & Semerjian, G. (2006) · Journal of Statistical Physics · doi:10.1007/s10955-006-9103-1 · Cited by 102
Intensively connected spin glasses: towards a replica-symmetry-breaking solution of the ground state
Wong, K. Y. M., & Sherrington, D. (1988) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/21/8/006 · Cited by 85
Landscape of Solutions in Constraint Satisfaction Problems
Mézard, M., Palassini, M., & Rivoire, O. (2005) · Physical Review Letters · doi:10.1103/physrevlett.95.200202 · Cited by 77
Survey-propagation decimation through distributed local computations
Chavas, J., Furtlehner, C., Mézard, M., & Zecchina, R. (2005) · Journal of Statistical Mechanics Theory and Experiment · doi:10.1088/1742-5468/2005/11/p11016 · Cited by 65
Krząkała, F., Pagnani, A., & Weigt, M. (2004) · Physical Review E · doi:10.1103/physreve.70.046705 · Cited by 59
Self-citationThe finite connectivity spin glass: investigation of replica symmetry breaking of the ground state
Goldschmidt, Y. Y., & Lai, P.-Y. (1990) · Journal of Physics A Mathematical and General · doi:10.1088/0305-4470/23/15/014 · Cited by 44
Relaxation in graph coloring and satisfiability problems
Svenson, P., & Nordahl, M. G. (1999) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.59.3983 · Cited by 42
Random graph coloring: Statistical physics approach
van Mourik, J., & Saad, D. (2002) · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · doi:10.1103/physreve.66.056120 · Cited by 40
(2015) · Chapman & Hall/CRC eBooks · doi:10.1201/b18378-14 · Cited by 35
Marginal states in mean-field glasses
Müller, M., Leuzzi, L., & Crisanti, A. (2006) · Physical Review B · doi:10.1103/physrevb.74.134431 · Cited by 32
Castellani, T., Krząkała, F., & Ricci‐Tersenghi, F. (2005) · The European Physical Journal B · doi:10.1140/epjb/e2005-00293-1 · Cited by 31
Self-citation
Cited by
Critical phenomena in complex networks
Dorogovtsev, S. N., Goltsev, A. V., & Mendes, J. F. F. (2008) · Reviews of Modern Physics · doi:10.1103/revmodphys.80.1275 · Cited by 2,220
Information, Physics, and Computation
Mézard, M., & Montanari, A. (2009) · doi:10.1093/acprof:oso/9780198570837.001.0001 · Cited by 1,913
Decelle, A., Krzakala, F., Moore, C., & Zdeborová, L. (2011) · Physical Review E · doi:10.1103/physreve.84.066106 · Cited by 747
Self-citationMean-field theory of hard sphere glasses and jamming
Parisi, G., & Zamponi, F. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.789 · Cited by 705
Statistical physics of inference: thresholds and algorithms
Zdeborová, L., & Krzakala, F. (2016) · Advances in Physics · doi:10.1080/00018732.2016.1211393 · Cited by 440
Self-citation
Metadata
- Authors
- Zdeborová, L., & Krząkała, F.
- Venue
- Physical Review E
- Publisher
- American Physical Society (APS)
- Published
- 2007-09-26
- Volume
- 76
- Issue
- 3
- Pages
- 031131-031131
- ISSN
- 1539-3755 (ISSN-L)
- 1550-2376
- OpenAlex
- W2105546154
- Cited by
- 306
- References
- 72
- FWCI
- 37.80
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.