A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
Version 1 / Nov 18, 2026/ arXiv: 2608.30604 / CC BY 4.0
Abstract
The cochromatic number of a graph is the least number of parts in a partition of into cliques and independent sets, so . Erdős and Gimbel asked whether with high probability for . Heckel answered this affirmatively for about of all integers and conjectured that the natural order of the difference along the full sequence is . We prove that, as through all integers, with high probability. The failure probabilities are summable, so under any coupling of the graphs the bound holds almost surely for all sufficiently large .
The proof counts partitions of the vertex set into classes of five consecutive sizes, each class declared independent or complete. The two choices per class outweigh the entropy lost by restricting the class sizes, so the expected number of such partitions is large already at a number of classes that lies order below the first-moment lower bound for the chromatic number, uniformly in the rounding phase. A second-moment argument, which controls all overlaps between two such partitions, including whole shared classes and large intersections of unequal classes, bounds the probability that such a partition exists from below. Vertex-exposure concentration, together with a coloring of the leftover vertices, then raises this to high probability at a cost of extra classes.
Provenance statement
Formalizations
Tools used
- OpenAI
- ChatGPTVersion GPT-5.6 Sol
- OpenAI
- CodexVersion GPT-5.6 Sol
- Lean
- LeanVersion Lean 4 with Mathlib
- Harmonic
- Aristotle
References
- Tudor Achim, Alex Best, Alberto Bietti, Kevin Der, Math ï s F é d é rico, Sergei Gukov, Daniel Halpern-Leistner, Kirsten Henningsgard, Yury Kudryashov, Alexander Meiburg, Martin Michelsen, Riley Patterson, Eric Rodriguez, Laura Scharff, Vikram Shanker, Vladmir Sicca, Hari Sowrirajan, Aidan Swope, Matyas Tamas, Vlad Tenev, Jonathan Thomm, Harold Williams, and Lawrence Wu. Aristotle : IMO -level automated theorem proving, 2025. URL https://doi.org/10.48550/arXiv.2510.01346.DOI
- Thomas F. Bloom. Erd ő s problem #625. https://www.erdosproblems.com/625, 2026. Accessed 16 July 2026.link
- B é la Bollob á s. The chromatic number of random graphs. Combinatorica , 8 0 (1): 0 49--55, 1988. 10.1007/BF02122551. URL https://doi.org/10.1007/BF02122551.DOI
- B é la Bollob á s and Paul Erd ő s. Cliques in random graphs. Mathematical Proceedings of the Cambridge Philosophical Society , 80 0 (3): 0 419--427, 1976. 10.1017/S0305004100053056. URL https://doi.org/10.1017/S0305004100053056.DOI
- B é la Bollob á s and Andrew Thomason. Generalized chromatic numbers of random graphs. Random Structures & Algorithms , 6 0 (2--3): 0 353--356, 1995. 10.1002/rsa.3240060222. URL https://doi.org/10.1002/rsa.3240060222.DOI
- Paul Erd ő s and John Gimbel. Some problems and results in cochromatic theory. In John Gimbel, John W. Kennedy, and Louis V. Quintas, editors, Quo Vadis, Graph Theory? , volume 55 of Annals of Discrete Mathematics , pages 261--264. North-Holland/Elsevier, 1993. 10.1016/S0167-5060(08)70393-5. URL https://doi.org/10.1016/S0167-5060(08)70393-5.DOI
- John Gimbel. Some of my favorite coloring problems for graphs and digraphs. In Ralucca Gera, Stephen T. Hedetniemi, and Craig Larson, editors, Graph Theory: Favorite Conjectures and Open Problems -- 1 , Problem Books in Mathematics, pages 95--108. Springer, Cham, 2016. ISBN 978-3-319-31940-7. 10.1007/978-3-319-31940-7_7. URL https://doi.org/10.1007/978-3-319-31940-7_7.DOI
- Geoffrey R. Grimmett and Colin J. H. McDiarmid. On colouring random graphs. Mathematical Proceedings of the Cambridge Philosophical Society , 77 0 (2): 0 313--324, 1975. 10.1017/S0305004100051124. URL https://doi.org/10.1017/S0305004100051124.DOI
- Annika Heckel. The chromatic number of dense random graphs. Random Structures & Algorithms , 53 0 (1): 0 140--182, 2018. 10.1002/rsa.20757. URL https://doi.org/10.1002/rsa.20757.DOI
- Annika Heckel. On a question of Erd ő s and Gimbel on the cochromatic number. The Electronic Journal of Combinatorics , 31 0 (4): 0 P4.72, 2024. 10.37236/13346. URL https://doi.org/10.37236/13346.DOI
Show all 21 referencesShow fewer references
- Annika Heckel. The difference between the chromatic and the cochromatic number of a random graph, 2025. URL https://arxiv.org/abs/2409.17614. Version 2, revised 19 February 2025; first submitted in 2024.link
- Annika Heckel and Konstantinos Panagiotou. Colouring random graphs: Tame colourings, 2023. URL https://arxiv.org/abs/2306.07253.link
- Colin McDiarmid. On the method of bounded differences. In Johannes Siemons, editor, Surveys in Combinatorics, 1989 , volume 141 of London Mathematical Society Lecture Note Series , pages 148--188. Cambridge University Press, 1989. 10.1017/CBO9781107359949.008. URL https://doi.org/10.1017/CBO9781107359949.008.DOI
- Colin McDiarmid. On the chromatic number of random graphs. Random Structures & Algorithms , 1 0 (4): 0 435--442, 1990. 10.1002/rsa.3240010404. URL https://doi.org/10.1002/rsa.3240010404.DOI
- Colin McDiarmid. Concentration. In Michel Habib, Colin McDiarmid, Jorge Ramirez-Alfonsin, and Bruce Reed, editors, Probabilistic Methods for Algorithmic Discrete Mathematics , volume 16 of Algorithms and Combinatorics , pages 195--248. Springer, Berlin, Heidelberg, 1998. 10.1007/978-3-662-12788-9_6. URL https://cgm.cs.mcgill.ca/~breed/conc/colin.pdf. Theorem 3.1; author preprint, pp. 10--11.DOI
- Konstantinos Panagiotou and Angelika Steger. A note on the chromatic number of a dense random graph. Discrete Mathematics , 309 0 (10): 0 3420--3423, 2009. 10.1016/j.disc.2008.09.019. URL https://doi.org/10.1016/j.disc.2008.09.019.DOI
- Samuil Petkov. Erd ő s Problem 625 : Lean 4 formalization and reproducibility record. Software companion at exact Git revisions, 2026. URL https://github.com/SamPetkov/Erdos/commit/31bbe00c529a996bdb61b880120d71240172d18f. Formal source revision 824e4b609466d2e26b216a76ecf103184dac2663; replay and archive revision 31bbe00c529a996bdb61b880120d71240172d18f; Lean and Mathlib v4.31.0.link
- Edward R. Scheinerman. Generalized chromatic numbers of random graphs. SIAM Journal on Discrete Mathematics , 5 0 (1): 0 74--80, 1992. 10.1137/0405006. URL https://doi.org/10.1137/0405006.DOI
- Alex Scott. On the concentration of the chromatic number of random graphs, 2017. URL https://arxiv.org/abs/0806.0178. Version 2; first submitted in 2008.link
- Raphael Steiner. On the difference between the chromatic and cochromatic number. SIAM Journal on Discrete Mathematics , 39 0 (4): 0 2268--2274, 2025. 10.1137/24M1715180. URL https://doi.org/10.1137/24M1715180. Published online 17 November 2025; arXiv:2408.02400.arXivDOI
- Yaming Yu. Relative log-concavity and a pair of triangle inequalities. Bernoulli , 16 0 (2): 0 459--470, 2010. 10.3150/09-BEJ216. URL https://doi.org/10.3150/09-BEJ216.DOI
Version history
- v1 · 53 pagesSubmitted by Samuil PetkovThis is version 2 of arXiv:2608.30604 (https://arxiv.org/abs/2608.30604). A Lean 4 formalization of an earlier version of the main theorem, with the weaker constant ((ln 2)^2/4) ln(200/153) ≈ 0.032 in place of 0.063, is registered on Palomar as PALOMAR-2026-09-02-000006: https://palomar-registry.org/entry?id=PALOMAR-2026-09-02-000006&version=1 . The improved constant 0.063 of this version is not formalized.CurrentNov 17, 2026