no. 16 · Tuesday 17 November 2026
A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
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.
- comments
- 53 pages, 3 figures. Companion Lean 4 formalization and reproducibility record at the cited exact software revision
- fields
- Combinatorics, Probability