A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
Samuil Petkov
math.CO
Aug 31, 2026 · v2
math.PR
TL;DR
A companion Lean 4/Mathlib development kernel-checks a weaker full-sequence version of the chromatic–cochromatic gap bound, with AI-assisted proof search via Aristotle.
Abstract
The cochromatic number $ζ(G)$ of a graph $G$ is the least number of parts in a partition of $V(G)$ into cliques and independent sets, so $ζ(G)\leχ(G)$. Erdős and Gimbel asked whether $χ(G_n)-ζ(G_n)\to\infty$ with high probability for $G_n\sim G(n,1/2)$. Heckel answered this affirmatively for about $95\%$ of all integers $n$ and conjectured that the natural order of the difference along the full sequence is $n/(\ln n)^3$. We prove that, as $n\to\infty$ through all integers, $χ(G_n)-ζ(G_n)\ge0.063\,n/(\ln n)^3$ with high probability. The failure probabilities are summable, so under any coupling of the graphs $G_n$ the bound holds almost surely for all sufficiently large $n$. 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 $n/(\ln n)^3$ 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 $o(n/(\ln n)^3)$ extra classes.
Problem
Erdős and Gimbel asked whether χ(G_n) − ζ(G_n) → ∞ with high probability for G_n G(n,1/2). Heckel resolved this for about 95% of integers n and conjectured that the difference is of order n/(ln n)^3 along the full sequence.
Approach
The proof counts partitions of the vertex set into classes of five consecutive sizes, each class declared independent or complete. The factor of two per class outweighs the entropy lost by restricting class sizes. A second-moment argument controls all overlaps between pairs of partitions, and vertex-exposure concentration plus a coloring of leftover vertices lifts the result to high probability. A Lean 4 development, with candidate code from GPT and proof search by Harmonic's Aristotle, kernel-checks a weaker version of the main bound.
Results
With high probability, χ(G_n) − ζ(G_n) ≥ 0.063 n/(ln n)^3 for all n, with summable failure probabilities. The Lean theorem certifies the weaker coefficient ((log 2)^2/4)·log(200/153). The phase-resolved refinement and the failure-probability estimates are proved only in the manuscript.