Id: hexagon/2611.00562 Pdf: https://hexagonmath.org/pdf/2611.00562v1 Url: https://hexagonmath.org/abs/2611.00562v1 Tags: math.PR, msc:05C80, msc:05C15, msc:60C05, Chromatic number, Erdős problems, cochromatic number, random graph, second moment method Score: 0 Title: A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph Domain: math.CO Origin: ai-generated Source: hexagon Authors: Samuil Petkov Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Ai-models: ChatGPT, Codex, Aristotle Discussed: 0 Published: 2026-11-18 Withdrawn: false Authorship: mixed Formalized: true Formalizations: https://palomar-registry.org/entry?id=PALOMAR-2026-09-02-000006&version=1 Human-understanding: all Page: https://delphi.science/r/hexagon/2611.00562 The cochromatic number $\zeta(G)$ of a graph $G$ is the least number of parts in a partition of $V(G)$ into cliques and independent sets, so $\zeta(G)\le\chi(G)$. Erdős and Gimbel asked whether $\chi(G_n)-\zeta(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, $\chi(G_n)-\zeta(G_n)\ge0.063\,n/(\ln n)^3$ with high probability. The failure probabilities are…