HEXAGONbeta

Existence of the qq-Colorability Threshold for Sparse Random Graphs

Primarily AI-generated textHuman understanding: some partsmath.PR — Probability

Contributed by P. M. Aronow ↗, Patrick Lopatto ↗

Version 1 / Oct 29, 2026 / CC BY 4.0

Abstract

For a fixed integer q≥3q \ge 3, we call a graph qq-colorable if its vertices admit qq colors with adjacent vertices colored differently. We prove that there exists dq>0d_q > 0 such that the random graph on nn vertices with independent edge probability d/nd/n is qq-colorable with probability tending to one for fixed 0≤d<dq0 \le d < d_q and to zero for fixed d>dqd > d_q, as n→∞n \to \infty. The same holds for the uniform random graph with ⌊cn⌋\lfloor cn \rfloor edges, for fixed c≥0c \ge 0, with threshold dq/2d_q/2 in cc. For fixed ϵ∈(0,1)\epsilon \in (0, 1), the first loss of colorability under independent uniform additions of pairs of distinct vertices lies with probability at least 1−ϵ1 - \epsilon in a deterministic window of Oq,ϵ(n(log⁡n)−3/2)O_{q, \epsilon}(n(\log n)^{-3/2}) steps, where log⁡\log 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

Proof discovery and verification were done with a combination of Opus 5.5, GPT 6 Astra, GPT Luna 6, and GPT 6.1 Sol. The results were formalized in Lean 4 by Opus 5.5, Luna 6, and GPT Sol 6.1. The writing was done by Opus 5.5, GPT 6.1 Sol, and Astra 6.

References

  1. 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
  2. Achlioptas, Dimitris; Friedgut, Ehud. A sharp threshold for kk-colorability. Random Structures & Algorithms, vol. 14, no. 1, pp. 63–70. 1999DOI
  3. 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
  4. 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
  5. 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
  6. 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
  7. Aldous, David J. Threshold limits for cover times. Journal of Theoretical Probability, vol. 4, no. 1, pp. 197–211. 1991DOI
  8. 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
  9. 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
  10. 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
  1. 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
  2. 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
  3. Boucheron, Stéphane; Lugosi, Gábor; Massart, Pascal. Concentration inequalities: a nonasymptotic theory of independence. Oxford University Press. 2013DOI
  4. 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
  5. 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
  6. Carenini, Gaia. A polynomial scaling window for random kk-SAT and a proof of the satisfiability conjecture. no. TR26–229. 2026. Preprint; October 5, 2026 reportlink
  7. Carenini, Gaia. The scaling window of random kk-SAT. no. TR26–145. 2026. Preprint, arXiv version 1, August 11, 2026; also ECCC TR26-145, published August 16, 2026arXiv
  8. Chvátal, Vášek. Almost all graphs with 1.44n1.44n edges are 3-colorable. Random Structures & Algorithms, vol. 2, no. 1, pp. 11–28. 1991DOI
  9. 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
  10. Coja-Oghlan, Amin. Upper-bounding the kk-colorability threshold by counting covers. The Electronic Journal of Combinatorics, vol. 20, no. 3, pp. P32. 2013arXivDOI
  11. 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 kk-colorability threshold, FOCS 2013, pp. 380–389arXivDOI
  12. 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
  13. 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
  14. Culberson, Joseph; Gent, Ian. Frozen development in graph coloring. Theoretical Computer Science, vol. 265, no. 1–2, pp. 227–264. 2001DOI
  15. 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
  16. Ding, Jian; Sly, Allan; Sun, Nike. Proof of the satisfiability conjecture for large kk. Annals of Mathematics, vol. 196, no. 1, pp. 1–388. 2022DOI
  17. Dubois, Olivier; Mandler, Jacques. On the non-3-colourability of random graphs. 2002. Preprint, version 1, September 9, 2002arXiv
  18. Dubois, Olivier; Mandler, Jacques. The 3-XORSAT threshold. Comptes Rendus Mathématique, vol. 335, no. 11, pp. 963–966. 2002DOI
  19. Efron, Bradley; Stein, Charles. The jackknife estimate of variance. The Annals of Statistics, vol. 9, no. 3, pp. 586–596. 1981DOI
  20. 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
  21. 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
  22. Friedgut, Ehud. Sharp thresholds of graph properties, and the kk-SAT problem. Journal of the American Mathematical Society, vol. 12, no. 4, pp. 1017–1054. 1999. With an appendix by Jean BourgainDOI
  23. 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
  24. Frieze, Alan; Karoński, Michał. Introduction to random graphs. Cambridge University Press. 2016DOI
  25. Füredi, Zoltán; Ruzsa, Imre Z. Nearly subadditive sequences. Acta Mathematica Hungarica, vol. 161, no. 2, pp. 401–411. 2020arXivDOI
  26. Goerdt, Andreas. A threshold for unsatisfiability. Journal of Computer and System Sciences, vol. 53, no. 3, pp. 469–486. 1996DOI
  27. Grimmett, Geoffrey. Probability on Graphs: Random Processes on Graphs and Lattices. Cambridge University Press, vol. 8. 2018DOI
  28. 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
  29. 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
  30. Janson, Svante; Łuczak, Tomasz; Ruciński, Andrzej. Random graphs. John Wiley & Sons. 2000DOI
  31. 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
  32. Krzakala, Florent; Pagnani, Andrea; Weigt, Martin. Threshold values, stability analysis, and high-qq asymptotics for the coloring problem on random graphs. Physical Review E, vol. 70, pp. 046705. 2004arXivDOI
  33. 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
  34. 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
  35. 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
  36. Molloy, Michael. The freezing threshold for kk-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
  37. Monasson, Rémi; Zecchina, Riccardo. Entropy of the KK-satisfiability problem. Physical Review Letters, vol. 76, no. 21, pp. 3881–3885. 1996arXivDOI
  38. 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
  39. Mulet, Roberto; Pagnani, Andrea; Weigt, Martin; Zecchina, Riccardo. Coloring random graphs. Physical Review Letters, vol. 89, pp. 268701. 2002arXivDOI
  40. OpenAI. A sharp threshold bound for monotone graph properties. 2026. Unrefereed preprint; manuscript dated September 25, 2026; repository version 7ef5c0c. OpenAI Math Release preprintlink
  41. 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
  42. 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
  43. OpenAI. Variance of the random kk-SAT hitting time. 2026. Unrefereed preprint; manuscript dated September 27, 2026; repository version fd4aeeb. OpenAI Math Release preprintlink
  44. 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
  45. 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
  46. Pittel, Boris; Sorkin, Gregory B. The satisfiability threshold for kk-XORSAT. Combinatorics, Probability and Computing, vol. 25, no. 2, pp. 236–268. 2016DOI
  47. 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
  48. Read, Ronald C. An introduction to chromatic polynomials. Journal of Combinatorial Theory, vol. 4, no. 1, pp. 52–71. 1968DOI
  49. Russo, Lucio. An approximate zero-one law. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, vol. 61, no. 1, pp. 129–139. 1982DOI
  50. Semerjian, Guilhem. On the freezing of variables in random constraint satisfaction problems. Journal of Statistical Physics, vol. 130, no. 2, pp. 251–293. 2008arXivDOI
  51. Steele, J. Michael. An Efron–Stein inequality for nonsymmetric statistics. The Annals of Statistics, vol. 14, no. 2, pp. 753–758. 1986DOI
  52. Wilson, David B. On the critical exponents of random kk-SAT. Random Structures & Algorithms, vol. 21, no. 2, pp. 182–195. 2002arXivDOI
  53. Zdeborová, Lenka; Krzakala, Florent. Phase transitions in the coloring of random graphs. Physical Review E, vol. 76, pp. 031131. 2007arXivDOI

Version history

  1. v1Submitted by Patrick LopattoInitial depositCurrentOct 28, 2026