Erdős Problem #625

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.

Erdős Problem 625 --- ROUND-2

1) ROUND-2 OBJECTIVE

Path pursued: (C) obstruction / correction-by-reduction.

Round-1 recorded the classical asymptotics and the 2024 progress of Heckel and Steiner, but it still left a qualitative gap: why do anti-concentration statements about $\chi(G(n,1/2))$ control the random variable $\chi(G)-\zeta(G)$, and what exact obstruction remains to a full solution for all $n$?

In this round I prove a precise quantitative transfer lemma: small gap $\chi-\zeta$ forces near-concentration of $\chi$ in a short interval. This isolates the remaining obstruction sharply.

2) Round-1 FOUNDATION USED

I use the following Round-1 facts as fixed background:

• the definitions of $\chi(G)$ and $\zeta(G)$;
• the classical bounds \[ \frac{n}{2\log_2 n}\le \zeta(G)\le \chi(G)\le (1+o(1))\frac{n}{2\log_2 n} \] for $G\sim G(n,1/2)$;
• the Round-1 summary of recent progress by Steiner and Heckel showing that $\chi(G)-\zeta(G)$ is not bounded with high probability and that Heckel proves a positive answer for roughly $95\%$ of all $n$.

3) NEW INSIGHT / TOOL (ROUND-2)

The new tool is a quantitative concentration transfer lemma.

For fixed $m\ge 0$, define \[ q_{n,m}:=\Pr\left(\chi(G)-\zeta(G)>m\right), \qquad G\sim G(n,1/2). \] I prove:

1. for every integer $a$, \[ q_{n,m}\ge \Pr(\chi(G)\le a)\Pr(\chi(G)\ge a+m+1); \]
2. consequently, there exists an interval of width $m$ that contains $\chi(G)$ with probability at least $1-2\sqrt{q_{n,m}}$.

So if $\chi(G)-\zeta(G)\le m$ with high probability, then $\chi(G)$ must be concentrated, with high probability, in an interval of width $m$. This is the exact obstruction that remains.

4) ATTACK PLAN (ROUND-2)

The Round-1 obstacle was qualitative: recent work implies large gaps for infinitely many $n$ and for about $95\%$ of all $n$, but not for every $n$.

To sharpen this, I prove a deterministic-probabilistic lemma reducing the open problem to one precise question about fixed-width concentration of $\chi(G(n,1/2))$. The proof uses only three facts:

1. $\zeta(G)\le \chi(\overline G)$;
2. $\overline G$ has the same distribution as $G$ when $G\sim G(n,1/2)$;
3. Harris--FKG for increasing events in the edge-exposure product space.

5) WORK (ROUND-2)

Let $G\sim G(n,1/2)$ and let $\overline G$ denote its complement.

Lemma 1 (deterministic comparison).

For every graph $G$, \[ \zeta(G)\le \chi(\overline G). \]

Proof.

A proper colouring of $\overline G$ partitions $V(G)$ into independent sets of $\overline G$, equivalently into cliques of $G$. Such a partition is a valid cocolouring of $G$. Hence the minimum number of colours in a cocolouring is at most $\chi(\overline G)$. $\square$

Lemma 2 (quantitative transfer).

Fix an integer $m\ge 0$ and put \[ q_{n,m}:=\Pr\left(\chi(G)-\zeta(G)>m\right). \] Then for every integer $a$, \[ q_{n,m}\ge \Pr(\chi(G)\le a)\Pr(\chi(G)\ge a+m+1). \tag{1} \]

Proof.

Consider the events \[ A_a:=\{\chi(G)\ge a+m+1\}, \qquad B_a:=\{\chi(\overline G)\le a\}. \] The event $A_a$ is increasing in the edge set of $G$: adding edges cannot decrease $\chi(G)$.

The event $B_a$ is also increasing in the edge set of $G$: adding an edge to $G$ removes an edge from $\overline G$, and removing edges cannot increase $\chi(\overline G)$. Therefore $A_a$ and $B_a$ are both increasing events in the product probability space of edge indicators of $G$. By Harris--FKG, \[ \Pr(A_a\cap B_a)\ge \Pr(A_a)\Pr(B_a). \tag{2} \] Because $\overline G$ has the same distribution as $G(n,1/2)$, \[ \Pr(B_a)=\Pr(\chi(G)\le a). \tag{3} \] On the event $A_a\cap B_a$, Lemma 1 gives \[ \zeta(G)\le \chi(\overline G)\le a, \] while also $\chi(G)\ge a+m+1$. Hence \[ \chi(G)-\zeta(G)\ge m+1, \] so $A_a\cap B_a\subseteq \{\chi(G)-\zeta(G)>m\}$. Thus, using $2$ and $3$, \[ q_{n,m}\ge \Pr(A_a\cap B_a)\ge \Pr(\chi(G)\ge a+m+1)\Pr(\chi(G)\le a), \] which is exactly $1$. $\square$

Lemma 3 (concentration consequence).

For every $n$ and every integer $m\ge 0$, there exists an integer $a_n$ such that \[ \Pr\left(a_n\le \chi(G)\le a_n+m\right)\ge 1-2\sqrt{q_{n,m}}. \tag{4} \]

Proof.

Let \[ F(t):=\Pr(\chi(G)\le t). \] If $q_{n,m}=0$, choose $a_n$ minimal such that $F(a_n)>0$. Then $F(a_n-1)=0$, and applying Lemma 2 with $a=a_n$ gives $F(a_n)\left(1-F(a_n+m)\right)=0$. Since $F(a_n)>0$, we get $F(a_n+m)=1$, so \[ \Pr\left(a_n\le \chi(G)\le a_n+m\right)=1, \] which is exactly $4$. Thus it remains only to treat the case $q_{n,m}>0$.

Choose $a_n$ minimal such that \[ F(a_n)\ge \sqrt{q_{n,m}}. \] Then by minimality, \[ F(a_n-1)<\sqrt{q_{n,m}}. \tag{5} \] Apply Lemma 2 with $a=a_n$: \[ q_{n,m}\ge F(a_n)\left(1-F(a_n+m)\right). \] Since $F(a_n)\ge \sqrt{q_{n,m}}$, it follows that \[ 1-F(a_n+m)\le \sqrt{q_{n,m}}. \tag{6} \] Now \[ \Pr\left(a_n\le \chi(G)\le a_n+m\right) = F(a_n+m)-F(a_n-1). \] Using $5$ and $6$, \[ F(a_n+m)-F(a_n-1)\ge 1-\sqrt{q_{n,m}}-\sqrt{q_{n,m}} =1-2\sqrt{q_{n,m}}. \] This proves $4$. $\square$

Corollary 4.

If for some fixed $m$ one has \[ \Pr\left(\chi(G)-\zeta(G)\le m\right)\to 1, \] then there exists a sequence of intervals $I_n$ of width $m$ such that \[ \Pr\left(\chi(G)\in I_n\right)\to 1. \]

Proof.

This is immediate from Lemma 3, since in that case $q_{n,m}\to 0$. $\square$

Corollary 5.

If for some fixed $m$ and some $\delta>0$ every interval $I$ of width $m$ satisfies \[ \Pr(\chi(G)\in I)\le 1-\delta, \] then \[ \Pr\left(\chi(G)-\zeta(G)>m\right)\ge \delta^2/4. \]

Proof.

If $q_{n,m}<\delta^2/4$, then Lemma 3 would produce an interval of width $m$ containing $\chi(G)$ with probability $>1-\delta$, contradiction. $\square$

Interpretation.

The full Erdős--Gimbel problem is therefore reduced to the following sharply formulated obstruction:

For each fixed $m$, can $\chi(G(n,1/2))$ concentrate with probability $1-o(1)$ inside some interval of width $m$?

If the answer is no for every fixed $m$, then $\chi(G)-\zeta(G)\to\infty$ with high probability.

6) ADVERSARIAL VERIFICATION

• Monotonicity of $B_a=\{\chi(\overline G)\le a\}$. This is easy to get wrong because the event is phrased in terms of $\overline G$. But as edges are added to $G$, edges are removed from $\overline G$, and removing edges cannot increase chromatic number. So $B_a$ is indeed increasing in the coordinates of $G$.

• Use of complement symmetry. For $G\sim G(n,1/2)$, the complement $\overline G$ has the same distribution as $G$. This is essential in passing from $\Pr(B_a)$ to $\Pr(\chi(G)\le a)$.

• Endpoint conventions. I formulated the gap event as $\chi(G)-\zeta(G)>m$ and the interval as $[a_n,a_n+m]$. This matches the discrete inequality in Lemma 2: the upper tail is $\Pr(\chi\ge a+m+1)$.

• What the lemma does not prove. Lemma 3 does not itself show that $\chi(G)-\zeta(G)\to\infty$ with high probability. It shows instead that any failure of the conjecture must be accompanied by near-total concentration of $\chi(G)$ in a bounded-width interval. Thus it identifies the exact remaining obstruction.

7) FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The strict advance over Round-1 is a quantitative theorem: small cochromatic gap forces short-interval concentration of the chromatic number. This turns the open problem into a sharp fixed-width concentration problem for $\chi(G(n,1/2))$. That is a precise obstruction, rather than the looser heuristic connection recorded in Round-1.

8) COMPLETION ESTIMATE (MANDATORY)

COMPLETION: 55%

9) REFERENCES

• T. F. Bloom, Erdős Problem #625, erdosproblems.com/625, accessed 2026-03-07.
• R. Steiner, On the difference between the chromatic and cochromatic number, arXiv:2408.02400v2.
• A. Heckel, On a question of Erdős and Gimbel on the cochromatic number, Electron. J. Combin. 31 $2024$, P4.72.
• A. Heckel, The difference between the chromatic and the cochromatic number of a random graph, arXiv:2409.17614v2.
• N. Alon and J. H. Spencer, The Probabilistic Method, for the Harris--FKG inequality.

10) OUTPUT FORMAT

This section is written in drop-in LaTeX form and starts directly from \section{}, with no preamble.

Problem 625

FORMAL RESTATEMENT

For a graph $G$, the cochromatic number $\zeta(G)$ is the minimum number of colours in a vertex-colouring such that each colour class induces either a clique or an independent set. Let $\chi(G)$ be the usual chromatic number.

Let $G\sim G(n,1/2)$ be the Erdős--Rényi random graph. The question is whether \[ \chi(G)-\zeta(G)\to\infty \] with high probability (equivalently: for every fixed $M$, $\Pr[\chi(G)-\zeta(G)\ge M]\to 1$).

QUICK LITERATURE/CONTEXT CHECK

This is Erdős Problem #625 and is listed as open. It is classical that for $G\sim G(n,1/2)$, \[ \zeta(G)\le \chi(G)\le (1+o(1))\frac{n}{2\log_2 n}, \] and also $\zeta(G)\ge \frac{n}{2\log_2 n}$ follows from the fact that $G$ a.a.s. has clique number and independence number $<2\log_2 n$.

Recent progress $2024$ by Heckel and independently Steiner shows that $\chi(G)-\zeta(G)$ is not bounded with high probability; moreover, if $\chi(G)-\zeta(G)\le f(n)$ with high probability, then $f(n)\ge n^{1/2-o(1)}$ along an infinite sequence of $n$. Heckel further proved that for any $\varepsilon>0$ one has $\chi(G)-\zeta(G)\ge n^{1-\varepsilon}$ for roughly $95\%$ of all $n$, and conjectured the typical order $\asymp n/(\log n)^3$.

ATTACK PLAN

1. Record the standard asymptotic scale of $\chi(G)$ and the sandwich bounds on $\zeta(G)$.
2. Explain why these bounds alone do not decide whether $\chi(G)-\zeta(G)\to\infty$.
3. Summarize the strongest known partial results and indicate a concrete path that could prove the conjectured divergence (e.g. computing expectations/concentration of an auxiliary parameter that couples to $\zeta$).

WORK

(A) Baseline asymptotics.

A standard estimate for the random graph is \[ \chi(G(n,1/2)) = (1+o(1))\frac{n}{2\log_2 n}. \] Also, every cocolouring is a partition of $V(G)$ into parts each of which is either an independent set of $G$ or a clique of $G$. In $G(n,1/2)$, both the independence number $\alpha(G)$ and clique number $\omega(G)$ are a.a.s. $<2\log_2 n$, hence every colour class in a cocolouring has size $<2\log_2 n$. Therefore any cocolouring uses at least \[ \frac{n}{2\log_2 n} \] colours, giving $\zeta(G)\ge \frac{n}{2\log_2 n}$ a.a.s. Together with $\zeta(G)\le \chi(G)$, we have \[ \frac{n}{2\log_2 n}\ \le\ \zeta(G)\ \le\ \chi(G)\ \le\ (1+o(1))\frac{n}{2\log_2 n}. \] This shows $\chi$ and $\zeta$ are asymptotically of the same order, but leaves open whether their difference diverges.

(B) Why the classical bounds do not answer the question.

The above inequalities allow the difference $\chi(G)-\zeta(G)$ to be as small as $0$ and as large as, say, $o\left(\tfrac{n}{\log n}\right)$ without contradicting asymptotic order. To prove divergence one needs a quantitative separation between the optimal pure independent-set partition and the optimal mixed clique/independent partition.

(C) Present strongest known progress and a plausible route.

The recent results indicate that the difference is not bounded w.h.p. and can be as large as $n^{1/2-o(1)}$ on infinitely many $n$ (and even $n^{1-\varepsilon}$ for most $n$). These results are consistent with the conjecture that typically \[ \chi(G)-\zeta(G) \asymp \frac{n}{(\log n)^3}, \] which would in particular imply $\chi(G)-\zeta(G)\to\infty$.

A concrete strategy discussed informally in the literature is to couple $\zeta(G)$ to an auxiliary random variable defined via two independent random graphs $G_1,G_2\sim G(n,1/2)$: let $X$ be the minimum $k$ such that $[n]$ can be partitioned into $k$ sets, each of which is an independent set in either $G_1$ or $G_2$. One may compare $X$ to $\zeta(G)$ by a coupling argument and then try to compute $\mathbb E[X]$ and prove concentration of $X$ around its mean; combined with known concentration for $\chi(G)$, a separation of expectations of order $\omega(1)$ would yield the desired divergence.

VERIFICATION

The inequalities in (A) are standard consequences of the typical size of $\alpha(G)$ and $\omega(G)$ and the classical asymptotics for $\chi(G(n,1/2))$. The remaining steps (B)--(C) are not proofs but identify what additional quantitative input is required.

FINAL

UNRESOLVED.

• (i) What was proved: The classical sandwich bounds $\frac{n}{2\log_2 n}\le \zeta(G)\le \chi(G)\le (1+o(1))\frac{n}{2\log_2 n}$ for $G\sim G(n,1/2)$.
• (ii) Strongest partial result stated here: Recent work (Heckel; Steiner) implies $\chi(G)-\zeta(G)$ is not bounded with high probability, and Heckel gives polynomial lower bounds for most $n$.
• (iii) First gap: None of the cited results imply that for every fixed $M$ we have $\Pr[\chi(G)-\zeta(G)\ge M]\to 1$; they allow the possibility that the difference is small on an infinite subsequence of $n$ with non-negligible probability.
• (iv) Next concrete step: Prove concentration and asymptotics for a variable tightly coupled to $\zeta(G)$ (e.g. the two-graph partition parameter $X$) to within an additive $o(1)$ or $o(n^{1/2})$ window, and separate its expectation from $\mathbb E[\chi(G)]$ by $\omega(1)$.

COMPLETION ESTIMATE

COMPLETION: 30%.