{"id":"arxiv/2608.30604","url":"https://arxiv.org/abs/2608.30604","tags":["math.CO","math.PR"],"score":0,"title":"A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph","domain":"math.CO","source":"arxiv","authors":["Samuil Petkov"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-31","reactions":{}}