A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph

Source abstract

Let $ζ(G)$ denote the minimum number of parts in a partition of $V(G)$ in which every part induces either a clique or an independent set. Erdős and Gimbel asked whether, for $G_n\sim G(n,1/2)$, the difference $χ(G_n)-ζ(G_n)$ tends to infinity with high probability. We resolve this problem along the full sequence $n\to\infty$ and prove that $\mathbb P(χ(G_n)-ζ(G_n)\ge ((\log 2)^2/4)\log(200/153)\,n/(\log n)^3)\to1$. This gives a lower bound at the conjectured scale $n/(\log n)^3$. We also obtain a phase-resolved refinement: if $δ_n$ is the fractional part of the standard independence-number center, then the coefficient may be replaced by $(\log 2)^2A_4(δ_n)/4-o(1)$, where $A_4$ is explicit, continuous, nonconstant, and satisfies $A_4(δ)>\log(200/153)$ for every $δ\in[0,1]$. The proof uses signed cocoloring profiles supported on four consecutive class sizes and remains uniform across jumps of the natural class-size cutoff. An exact signed-overlap identity separates local cell rewards from a binary cycle-space factor. A canonical decomposition into high cells and a capped residual matching, together with an endpoint-table comparison and an injective restriction of residual even edge sets, yields the required second-moment bound. A bounded-differences argument then amplifies the resulting rare signed witness to a high-probability cocoloring.