GPT 6 Astra Ultra attempt on Math-5776

Erdős Problem 625: an exact overlap calculation for cocolourings

Statement and current context

For $G\sim G(n,1/2)$, let $\chi(G)$ be its chromatic number and $\zeta(G)$ the minimum number of parts in a partition into cliques or independent sets. The question asks whether $\chi(G)-\zeta(G)\to\infty$ with probability tending to one, along the full sequence of integers $n$. The current problem page reports a full-sequence resolution by Petkov and GPT-5.6. The linked manuscript proposes a lower bound of order $n/(\log n)^3$. This attempt does not claim to reproduce or independently verify that entire argument. It proves an exact signed-overlap identity, explains a necessary cycle correction, and gives a rigorous concentration criterion sufficient to finish the problem if an expectation gap is established.

1. Signed witnesses

A signed witness is a partition $\Pi$ of $[n]$ with every part marked either $I$ or $K$. It is valid if every $I$-part is independent and every $K$-part is a clique. For a partition with $r$ parts put \[ E(\Pi)=\sum_{A\in\Pi}\binom{|A|}{2}. \] A fixed marking is valid with probability $2^{-E(\Pi)}$, since it prescribes distinct edge coordinates. Summing over all markings gives expected signed-witness count $2^{r-E(\Pi)}$. Marks on singleton parts are still counted separately; this harmless convention makes the identities exact.

Take two partitions $\Pi=(A_1,\ldots,A_r)$ and $\Pi'=(B_1,\ldots,B_{r'})$, and put $t_{ij}=|A_i\cap B_j|$. Form a bipartite graph $H$ on the $r+r'$ part labels, placing an edge $ij$ exactly when $t_{ij}\ge2$. Let $e(H),v(H),c(H)$ be its numbers of edges, vertices, and connected components, with isolated vertices counted. Set $\beta(H)=e(H)-v(H)+c(H)$. A marking of the two partitions is compatible exactly when the signs agree across every edge of $H$: an intersection with at least two vertices prescribes a common graph edge, while smaller intersections impose no condition. Therefore there are precisely $2^{c(H)}$ compatible pairs of markings. For each compatible pair, the number of distinct prescribed edge coordinates is \[ E(\Pi)+E(\Pi')-\sum_{i,j}\binom{t_{ij}}2. \] After summing joint probabilities and dividing by the two individual signed expectations, the resulting overlap factor is \begin{align*} W(\Pi,\Pi') &=2^{\sum_{i,j}\binom{t_{ij}}2-r-r'+c(H)}\\ &=\boxed{2^{\,\beta(H)+\sum_{t_{ij}\ge2}(\binom{t_{ij}}2-1)}}. \tag{1} \end{align*} This derivation proves every factor, including the component count.

2. Exact second moment and a check on the cycle correction

Fix any class-size profile, and let $\mathcal P$ be its set of partitions, with an unambiguous fixed convention for ordering parts. All such partitions have the same $r$ and $E$. Let $Z$ count valid signed witnesses over $\mathcal P$. Then \[ \mathbb EZ=|\mathcal P|2^{r-E},\qquad \frac{\mathbb EZ^2}{(\mathbb EZ)^2} =\frac1{|\mathcal P|^2}\sum_{\Pi,\Pi'\in\mathcal P}W(\Pi,\Pi'). \tag{2} \] The factor $2^{\beta(H)}$ cannot be dropped. For $n=8$, let both partitions have two parts of size four, with all four intersections of size two. Then $H=K_{2,2}$, so $\beta(H)=1$, while every local exponent $\binom22-1$ is zero. Formula $1$ gives $W=2$, not one. Equivalently, the four overlap constraints admit two common signings instead of the one that four independent constraints on four signs would suggest. This is a concrete obstruction to a second-moment argument that treats the cells independently.

3. A concentration criterion for the required gap

Expose the random graph in $n$ independent blocks, block $i$ containing all edges $ij$ with $j>i$. Changing one block changes only edges incident with vertex $i$. If two such graphs share the same graph $J$ after deleting $i$, each of $\chi$ and $\zeta$ lies between its value on $J$ and that value plus one. Consequently changing one block changes either parameter by at most one and their difference $D=\chi-\zeta$ by at most two. The bounded-differences inequality therefore gives \[ \Pr\left(D\le\mathbb ED-t\right)\le e^{-t^2/(2n)}. \tag{3} \] For example, if one proves $\mathbb ED/\sqrt n\to\infty$, then putting $t=\mathbb ED/2$ proves $D\to\infty$ with probability tending to one. In particular an expectation lower bound $\mathbb ED\ge c n/(\log n)^3$ would suffice, since $\sqrt n/(\log n)^3\to\infty$. Neither $1$ nor the first moment alone proves this expectation lower bound. Cauchy--Schwarz applied to $Z\mathbf1_{Z>0}$ only gives \[ \Pr(Z>0)\ge (\mathbb EZ)^2/\mathbb EZ^2. \] To make it useful, the complete average in $2$ must be controlled, including large intersections and cycle factors, uniformly across changes in the optimal integer class sizes. This is precisely the substantial estimate not established in this attempt.

4. What a weaker concentration transfer cannot show

The deterministic inequality $\zeta(G)\le\chi(\overline G)$ and Harris's inequality imply, for integer $m,a$, \[ \Pr(D>m)\ge\Pr(\chi(G)\le a)\Pr(\chi(G)\ge a+m+1). \] Both events $\{\chi(G)\ge a+m+1\}$ and $\{\chi(\overline G)\le a\}$ are increasing in the edge coordinates of $G$, which proves the assertion. However, a fixed positive lower bound obtained this way for $\Pr(D>m)$ does not imply that this probability tends to one. It rules out one type of concentration; it does not by itself resolve the full-sequence question. Keeping that quantifier distinction prevents an incorrect conclusion from an otherwise valid transfer lemma.

Conclusion and sources

Attempt status: unresolved. The exact overlap identity $1$--$2$, its nontrivial cycle example, and the sufficient concentration criterion $3$ are proved. A uniform bound on the profile-overlap average strong enough to produce a diverging gap is still missing here. The database's reported resolution and this attempt's proof coverage are separate statements.

• https://www.erdosproblems.com/625, checked 24 September 2026.
• S. Petkov, A full-sequence quantitative gap between the chromatic and cochromatic numbers of a random graph, linked manuscript, https://github.com/SamPetkov/Erdos/blob/main/625/arxiv_625.pdf. Its signed-witness framework motivates the reconstruction above; the manuscript's complete second-moment claim is not assumed as a theorem here.

Completion estimate: 50%; the full-sequence second-moment/expectation gap is not proved.