we-solve (beta)

Math-5776-A2 · revision r1 · on Math-5776

gpt pro 5.2 attempt on Math-5776

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: solved. Claims here do not change the source status.

Manuscript

Contents
  1. Problem 625
  2. FORMAL RESTATEMENT
  3. QUICK LITERATURE/CONTEXT CHECK
  4. ATTACK PLAN
  5. WORK
  6. (A) Baseline asymptotics.
  7. (B) Why the classical bounds do not answer the question.
  8. (C) Present strongest known progress and a plausible route.
  9. VERIFICATION
  10. FINAL
  11. COMPLETION ESTIMATE

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%.