Existence of the -Colorability Threshold for Sparse Random Graphs
Version 1 / Oct 29, 2026 / CC BY 4.0
Abstract
For a fixed integer , we call a graph -colorable if its vertices admit colors with adjacent vertices colored differently. We prove that there exists such that the random graph on vertices with independent edge probability is -colorable with probability tending to one for fixed and to zero for fixed , as . The same holds for the uniform random graph with edges, for fixed , with threshold in . For fixed , the first loss of colorability under independent uniform additions of pairs of distinct vertices lies with probability at least in a deterministic window of steps, where is natural. The proof uses interpolation to establish convergence and bounds the expected number of pairs needed to destroy colorability of the last colorable graph by identifying random vertices and controlling the growth of classes equal in every coloring.
Provenance statement
References
- Abbe, Emmanuel; Montanari, Andrea. On the concentration of the number of solutions of random satisfiability formulas. Random Structures & Algorithms, vol. 45, no. 3, pp. 362–382. 2014. Published online April 12, 2013arXivDOI
- Achlioptas, Dimitris; Friedgut, Ehud. A sharp threshold for -colorability. Random Structures & Algorithms, vol. 14, no. 1, pp. 63–70. 1999DOI
- Achlioptas, Dimitris; Molloy, Michael. The analysis of a list-coloring algorithm on a random graph. Proceedings of the 38th Annual Symposium on Foundations of Computer Science, pp. 204–212. 1997DOI
- Achlioptas, Dimitris; Moore, Cristopher. Almost all graphs with average degree 4 are 3-colorable. Journal of Computer and System Sciences, vol. 67, no. 2, pp. 441–471. 2003DOI
- Achlioptas, Dimitris; Naor, Assaf. The two possible values of the chromatic number of a random graph. Annals of Mathematics, vol. 162, no. 3, pp. 1335–1351. 2005DOI
- Achlioptas, Dimitris; Ricci-Tersenghi, Federico. Random formulas have frozen variables. SIAM Journal on Computing, vol. 39, no. 1, pp. 260–280. 2009. Conference predecessor: On the solution-space geometry of random constraint satisfaction problems, STOC 2006, pp. 130–139DOI
- Aldous, David J. Threshold limits for cover times. Journal of Theoretical Probability, vol. 4, no. 1, pp. 197–211. 1991DOI
- Ayre, Peter; Coja-Oghlan, Amin; Greenhill, Catherine. Lower bounds on the chromatic number of random graphs. Combinatorica, vol. 42, pp. 617–658. 2022. Published online October 26, 2021arXivDOI
- Bapst, Victor; Coja-Oghlan, Amin; Hetterich, Samuel; Raßmann, Felicia; Vilenchik, Dan. The condensation phase transition in random graph coloring. Communications in Mathematical Physics, vol. 341, pp. 543–606. 2016arXivDOI
- Bayati, Mohsen; Gamarnik, David; Tetali, Prasad. Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. The Annals of Probability, vol. 41, no. 6, pp. 4080–4115. 2013arXivDOI
Show all 63 referencesShow fewer references
- Bollobás, Béla; Borgs, Christian; Chayes, Jennifer T.; Kim, Jeong Han; Wilson, David B. The scaling window of the 2-SAT transition. Random Structures & Algorithms, vol. 18, no. 3, pp. 201–256. 2001arXivDOI
- Boucheron, Stéphane; Bousquet, Olivier; Lugosi, Gábor; Massart, Pascal. Moment inequalities for functions of independent random variables. The Annals of Probability, vol. 33, no. 2, pp. 514–560. 2005arXivDOI
- Boucheron, Stéphane; Lugosi, Gábor; Massart, Pascal. Concentration inequalities: a nonasymptotic theory of independence. Oxford University Press. 2013DOI
- Bourgain, Jean; Kalai, Gil. Influences of variables and threshold intervals under group symmetries. Geometric and Functional Analysis, vol. 7, no. 3, pp. 438–461. 1997DOI
- Bourgain, Jean; Kalai, Gil. Threshold intervals under group symmetries. Convex Geometric Analysis, vol. 34, pp. 59–64. 1999. Author manuscript dated 1998, pp. 59–63; print edition 1999DOI
- Carenini, Gaia. A polynomial scaling window for random -SAT and a proof of the satisfiability conjecture. no. TR26–229. 2026. Preprint; October 5, 2026 reportlink
- Carenini, Gaia. The scaling window of random -SAT. no. TR26–145. 2026. Preprint, arXiv version 1, August 11, 2026; also ECCC TR26-145, published August 16, 2026arXiv
- Chvátal, Vášek. Almost all graphs with edges are 3-colorable. Random Structures & Algorithms, vol. 2, no. 1, pp. 11–28. 1991DOI
- Chvátal, Vášek; Reed, Bruce. Mick gets some (the odds are on his side). Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, pp. 620–627. 1992DOI
- Coja-Oghlan, Amin. Upper-bounding the -colorability threshold by counting covers. The Electronic Journal of Combinatorics, vol. 20, no. 3, pp. P32. 2013arXivDOI
- Coja-Oghlan, Amin; Vilenchik, Dan. The chromatic number of random graphs for most average degrees. International Mathematics Research Notices, vol. 2016, no. 19, pp. 5801–5859. 2016. Extended abstract: Chasing the -colorability threshold, FOCS 2013, pp. 380–389arXivDOI
- Coja-Oghlan, Amin; Efthymiou, Charilaos; Hetterich, Samuel. On the chromatic number of random regular graphs. Journal of Combinatorial Theory, Series B, vol. 116, pp. 367–439. 2016arXivDOI
- Coja-Oghlan, Amin; Krzakala, Florent; Perkins, Will; Zdeborová, Lenka. Information-theoretic thresholds from the cavity method. Advances in Mathematics, vol. 333, pp. 694–795. 2018arXivDOI
- Culberson, Joseph; Gent, Ian. Frozen development in graph coloring. Theoretical Computer Science, vol. 265, no. 1–2, pp. 227–264. 2001DOI
- de Bruijn, N. G.; Erdős, Paul. Some linear and some quadratic recursion formulas. II. Proceedings of the Koninklijke Nederlandse Akademie van Wetenschappen, Series A, vol. 55, pp. 152–163. 1952. Also Indagationes Mathematicae 14 (1952), 152–163; Theorems 22–23DOI
- Ding, Jian; Sly, Allan; Sun, Nike. Proof of the satisfiability conjecture for large . Annals of Mathematics, vol. 196, no. 1, pp. 1–388. 2022DOI
- Dubois, Olivier; Mandler, Jacques. On the non-3-colourability of random graphs. 2002. Preprint, version 1, September 9, 2002arXiv
- Dubois, Olivier; Mandler, Jacques. The 3-XORSAT threshold. Comptes Rendus Mathématique, vol. 335, no. 11, pp. 963–966. 2002DOI
- Efron, Bradley; Stein, Charles. The jackknife estimate of variance. The Annals of Statistics, vol. 9, no. 3, pp. 586–596. 1981DOI
- Erdős, Paul; Rényi, Alfréd. On the evolution of random graphs. A Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, vol. 5, pp. 17–61. 1960link
- Franz, Silvio; Leone, Michele. Replica bounds for optimization problems and diluted spin systems. Journal of Statistical Physics, vol. 111, no. 3–4, pp. 535–564. 2003arXivDOI
- Friedgut, Ehud. Sharp thresholds of graph properties, and the -SAT problem. Journal of the American Mathematical Society, vol. 12, no. 4, pp. 1017–1054. 1999. With an appendix by Jean BourgainDOI
- Friedgut, Ehud; Kalai, Gil. Every monotone graph property has a sharp threshold. Proceedings of the American Mathematical Society, vol. 124, no. 10, pp. 2993–3002. 1996DOI
- Frieze, Alan; Karoński, Michał. Introduction to random graphs. Cambridge University Press. 2016DOI
- Füredi, Zoltán; Ruzsa, Imre Z. Nearly subadditive sequences. Acta Mathematica Hungarica, vol. 161, no. 2, pp. 401–411. 2020arXivDOI
- Goerdt, Andreas. A threshold for unsatisfiability. Journal of Computer and System Sciences, vol. 53, no. 3, pp. 469–486. 1996DOI
- Grimmett, Geoffrey. Probability on Graphs: Random Processes on Graphs and Lattices. Cambridge University Press, vol. 8. 2018DOI
- Guerra, Francesco; Toninelli, Fabio Lucio. The thermodynamic limit in mean field spin glass models. Communications in Mathematical Physics, vol. 230, no. 1, pp. 71–79. 2002arXivDOI
- Hajek, Bruce. Hitting-time and occupation-time bounds implied by drift analysis with applications. Advances in Applied Probability, vol. 14, no. 3, pp. 502–525. 1982DOI
- Janson, Svante; Łuczak, Tomasz; Ruciński, Andrzej. Random graphs. John Wiley & Sons. 2000DOI
- Kaporis, Alexis C.; Kirousis, Lefteris M.; Stamatiou, Yannis C. A note on the non-colorability threshold of a random graph. The Electronic Journal of Combinatorics, vol. 7, no. 1, pp. R29. 2000DOI
- Krzakala, Florent; Pagnani, Andrea; Weigt, Martin. Threshold values, stability analysis, and high- asymptotics for the coloring problem on random graphs. Physical Review E, vol. 70, pp. 046705. 2004arXivDOI
- Krzakala, Florent; Montanari, Andrea; Ricci-Tersenghi, Federico; Semerjian, Guilhem; Zdeborová, Lenka. Gibbs states and the set of solutions of random constraint satisfaction problems. Proceedings of the National Academy of Sciences, vol. 104, no. 25, pp. 10318–10323. 2007arXivDOI
- Last, Günter; Penrose, Mathew. Lectures on the Poisson process. Cambridge University Press, vol. 7. 2018. First published 2018; Cambridge online publication October 26, 2017DOI
- Mecke, Joseph. Stationäre zufällige Maße auf lokalkompakten Abelschen Gruppen. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, vol. 9, no. 1, pp. 36–58. 1967DOI
- Molloy, Michael. The freezing threshold for -colourings of a random graph. Journal of the ACM, vol. 65, no. 2, pp. 7:1–7:62. 2018. A shorter version appeared in STOC 2012, pp. 921–930DOI
- Monasson, Rémi; Zecchina, Riccardo. Entropy of the -satisfiability problem. Physical Review Letters, vol. 76, no. 21, pp. 3881–3885. 1996arXivDOI
- Monasson, Rémi; Zecchina, Riccardo; Kirkpatrick, Scott; Selman, Bart; Troyansky, Lidror. Determining computational complexity from characteristic `phase transitions'. Nature, vol. 400, pp. 133–137. 1999DOI
- Mulet, Roberto; Pagnani, Andrea; Weigt, Martin; Zecchina, Riccardo. Coloring random graphs. Physical Review Letters, vol. 89, pp. 268701. 2002arXivDOI
- OpenAI. A sharp threshold bound for monotone graph properties. 2026. Unrefereed preprint; manuscript dated September 25, 2026; repository version 7ef5c0c. OpenAI Math Release preprintlink
- OpenAI. A limiting satisfiability threshold for every fixed clause size. 2026. Unrefereed preprint; manuscript dated September 25, 2026; repository version fd4aeeb. OpenAI Math Release preprintlink
- OpenAI. Linear variance of the random 3-SAT hitting time. 2026. Unrefereed preprint; manuscript dated October 5, 2026; repository version fd4aeeb. OpenAI Math Release preprintlink
- OpenAI. Variance of the random -SAT hitting time. 2026. Unrefereed preprint; manuscript dated September 27, 2026; repository version fd4aeeb. OpenAI Math Release preprintlink
- Panchenko, Dmitry; Talagrand, Michel. Bounds for diluted mean-fields spin glass models. Probability Theory and Related Fields, vol. 130, no. 3, pp. 319–336. 2004arXivDOI
- Perkins, Will. Searching for (sharp) thresholds in random structures: where are we now?. Bulletin of the American Mathematical Society, vol. 62, no. 1, pp. 113–143. 2025. Online publication October 30, 2024arXivDOI
- Pittel, Boris; Sorkin, Gregory B. The satisfiability threshold for -XORSAT. Combinatorics, Probability and Computing, vol. 25, no. 2, pp. 236–268. 2016DOI
- Pittel, Boris; Yeum, Ji-A. How frequently is a system of 2-linear Boolean equations solvable?. The Electronic Journal of Combinatorics, vol. 17, no. 1, pp. R92. 2010arXivDOI
- Read, Ronald C. An introduction to chromatic polynomials. Journal of Combinatorial Theory, vol. 4, no. 1, pp. 52–71. 1968DOI
- Russo, Lucio. An approximate zero-one law. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, vol. 61, no. 1, pp. 129–139. 1982DOI
- Semerjian, Guilhem. On the freezing of variables in random constraint satisfaction problems. Journal of Statistical Physics, vol. 130, no. 2, pp. 251–293. 2008arXivDOI
- Steele, J. Michael. An Efron–Stein inequality for nonsymmetric statistics. The Annals of Statistics, vol. 14, no. 2, pp. 753–758. 1986DOI
- Wilson, David B. On the critical exponents of random -SAT. Random Structures & Algorithms, vol. 21, no. 2, pp. 182–195. 2002arXivDOI
- Zdeborová, Lenka; Krzakala, Florent. Phase transitions in the coloring of random graphs. Physical Review E, vol. 76, pp. 031131. 2007arXivDOI
Version history
- v1 · 105 pagesSubmitted by Patrick LopattoInitial depositCurrentOct 28, 2026