Erdős #760 — large χ(G) forces a subgraph of large cochromatic number ζ(H) ≫ χ(G)/log χ(G)

Statement

The cochromatic number $\zeta(G)$ (written $z(G)$ in the source paper) of a graph $G=(V,E)$ is the minimum number of parts in a partition of $V$ such that each part either induces a complete graph or is an independent (edgeless) set.

Question (Erdős–Gimbel 1993)

if $G$ has chromatic number $\chi(G)=m$, must $G$ contain a subgraph $H$ with $$\zeta(H) \gg \frac{m}{\log m}\ ?$$ Erdős and Gimbel themselves proved the weaker bound $\zeta(H)\gg\sqrt{m/\log m}$ and conjectured the square root could be removed; the target bound is best possible, as witnessed by $G=K_m$ itself (erdosproblems.com/760).

Facts

- Origin: P. Erdős and J. Gimbel, "Some problems and results in cochromatic theory," in *Quo Vadis, Graph Theory?*, Annals of Discrete Mathematics 55 (1993), 261–264 [ErGi93] — they prove $\zeta(H)\gg\sqrt{m/\ln m}$ for some subgraph $H$, and conjecture the exponent-$1$ (no-square-root) bound; see also J. Gimbel, "Problem," Discrete Mathematics 101 (1992), 353–354. - Solved 1997 by Noga Alon, Michael Krivelevich, Benny Sudakov, "Subgraphs with a large cochromatic number," *J. Graph Theory* 25 (1997), 295–297 [AKS97] — a 3-page note, PDF at web.math.princeton.edu/~nalon/PDFS/cochrom2.pdf. - Answer: yes. Theorem 1.1 of [AKS97]: every graph $G$ with $\chi(G)=n$ contains a subgraph $H$ with $\zeta(H) \ge (\tfrac14+o(1))\,\dfrac{n}{\log_2 n}$. - Tightness: for $G=K_n$ ($\chi=n$), *every* subgraph $H\subseteq K_n$ has at most $n$ vertices, and the cochromatic number of *any* $n$-vertex graph is at most $(2+o(1))n/\log_2 n$ (Y. Caro, "On the covering number of combinatorial structures," Ars Combinatoria 29B (1990), 111–124; P. Erdős, J. Gimbel, D. Kratsch, "Some extremal results in cochromatic and dichromatic theory," J. Graph Theory 15 (1992), 579–585). So the $n/\log n$ rate (not just its existence) is settled up to the constant factor $\tfrac14$ vs $2$. - Formalized: a Lean solution auto-formalized by "Aristotle" (following the AKS97 paper) is linked from the erdosproblems.com/760 forum thread — gist: madeve-unipi/a7ae50d445f95e73c360f442c3c84143 (Erdos760.lean), viewable via live.lean-lang.org. - Related problems: erdos/57 — a different chromatic-number-forces-structure problem (odd cycles / $\sum 1/a_i \gg \log\chi$), same "large $\chi$ forces a rich sub-structure at rate $\log\chi$" shape but a different target statistic and a different (sublinear-expander) proof technique — useful contrast, not the same machinery.

Solution

Answer: yes — $\zeta(H)\ge(\tfrac14+o(1))\,n/\log_2 n$, proved by Alon–Krivelevich–Sudakov (1997) via a two-stage probabilistic (random-subgraph) argument. The whole proof is 1.5 pages; the technique is short, sharp, and highly transferable.

Step 1 — reduce to a bounded-size, near-full-chromatic subgraph (Lemma 2.1). Let $G$ have $\chi(G)=n$. If $G$ already has $\zeta(G)\ge n/\ln n$, done. Otherwise take an *optimal* cochromatic partition of $G$ into $k$ independent sets $U_i$ and $l$ cliques $W_j$ with $k+l<n/\ln n$. Discard the independent parts (they can serve as $k$ colour classes of *any* proper colouring — independent sets are trivially monochromatic), and let $G_1$ be the subgraph induced on $V_1=\bigcup_j W_j$ (the union of the clique parts only). Since $\chi(G)\le \chi(G_1)+k$ (colour $G_1$ optimally, reuse the $U_i$'s as extra colour classes), $\chi(G_1)\ge n-n/\ln n=(1+o(1))n$. And $|V_1|\le n^2/\ln n$ (using a WLOG assumption that $G$ has no $n$-clique, handled separately by a classical diagonal-Ramsey-number lower-bound argument — Erdős's original 1947 probabilistic construction, giving an $n$-vertex graph with neither clique nor independent set $\ge 2\log_2 n$, Graham–Rothschild–Spencer / Alon–Spencer). This step is a generic size-reduction trick: whenever a partition/covering statistic is small, most of the graph's vertices are "wasted" on independent parts that are colour-classes for free — discard them and the *remaining* graph (the union of the "hard" clique parts) must still carry almost all of the original chromatic number, but now on a polynomially-bounded vertex set.

Step 2 — the core trick: p=1/2 random subgraph kills large cliques AND kills large hidden-chromatic independent sets simultaneously (Lemma 2.2). Take $H\subseteq G_1$ by including each edge of $G_1$ independently with probability $1/2$. Two "bad events" are shown to be $o(1)$-probability by union bounds, over the $|V_1|\le n^2$ vertices: 1. No big clique survives. $\Pr[\exists$ clique of size $4\log_2 n$ in $H] \le \binom{n^2}{4\log_2 n}2^{-\binom{4\log_2 n}{2}} = o(1)$ — the standard $p=1/2$ random-graph clique-suppression bound (this is exactly the mechanism behind the classical probabilistic lower bound $R(k,k)\ge 2^{k/2}$ for diagonal Ramsey numbers). 2. No independent set of $H$ hides a stubbornly-high-chromatic induced subgraph of $G_1$. The key classical fact plugged in here: a $k$-chromatic colour-critical graph has minimum degree $\ge k-1$ (elementary — removing any vertex would otherwise still leave enough colours). So if some $V_0$ that is independent in $H$ had $\chi(G_1[V_0])>4\log_2n$, then $G_1[V_0]$ contains a colour-critical subgraph $G_2$ on some vertex set $V_2$ with $\delta(G_2)\ge 4\log_2n$ — i.e. $V_2$ is independent in $H$ *and* $G_1[V_2]$ has high minimum degree, meaning a large, structured set of edges of $G_1$ all had to independently fail to appear in $H$. A union bound over all candidate $V_2$ of every size $k$ from $4\log_2n$ to $n^2$ (using that $G_1[V_2]$ has $\ge k\cdot4\log_2n/2$ edges, each surviving-as-absent w.p. $1/2$) again gives total probability $o(1)$.

Step 3 — turn the two "almost-surely" structural guarantees into the chromatic-additivity inequality that forces $\zeta(H)$ up. Once (1) and (2) hold for $H$, take *any* optimal cochromatic partition of $H$ into $k$ independent sets $U_i$ and $l$ cliques $W_j$ (so $\zeta(H)=k+l$). By (1) each clique $W_j$ (a clique of $H$, hence of $G_1$) has $|W_j|<4\log_2n$ effectively bounding its colour cost by $4\log_2n$ colours (trivially, colour it with $|W_j|$ colours — but the *union-bound-controlled* quantity that matters is that $\chi(G_1[U_i])\le 4\log_2n$ by (2), the genuinely non-trivial half). Colouring each $U_i$ with $\le4\log_2n$ colours (by (2)) and each $W_j$ with $|W_j|\le$ (bounded, or trivially $\le 4\log_2 n$ after the clique-suppression event) colours gives a proper colouring of all of $G_1$ using $\le (k+l)\cdot 4\log_2n$ colours total: $$(1+o(1))n=\chi(G_1)\ \le\ \sum_i\chi(G_1[U_i]) + \sum_j|W_j|\ \le\ (k+l)\cdot 4\log_2n = \zeta(H)\cdot 4\log_2n,$$ i.e. $\zeta(H)\ge(1+o(1))n/(4\log_2n)$. $\blacksquare$

Why this is the transferable idea. The generic template — *(i) reduce to a bounded-size near-extremal instance by discarding the "free" part of an optimal solution to the statistic you're lower-bounding; (ii) take a $p=1/2$ (or other fixed-$p$) random subgraph and union-bound away two complementary bad events simultaneously — one controlling "large clean substructures survive" (here: no big clique), the other controlling "no complementary part can secretly still be hard" (here: no independent set hides high chromatic number, using that hard-to-colour = high-min-degree via colour-criticality); (iii) chain the surviving structural bounds through a trivial additivity/counting inequality (here: colouring cost adds over the partition) to force the target statistic up* — is a general two-sided probabilistic-deletion recipe for proving "large $\chi(G)$ forces a rich substructure at rate $\chi(G)/\log\chi(G)$" theorems. It reuses only elementary tools (union bound, $\binom{m}{k}\le(em/k)^k$, and the colour-critical-graph min-degree fact) rather than heavy machinery (no polynomial method, no regularity lemma, no expander mixing) — which is exactly why a 3-page note settled a conjecture that had stood since 1993.

Related

- erdos/57 — sibling "large $\chi(G)$ forces rich substructure at $\log\chi$ rate" problem (odd-cycle reciprocal-sum version), solved by a completely different technique (sublinear expanders, Liu–Montgomery 2020) — useful contrast showing the $n/\log n$-type rate recurs across chromatic-number-forcing problems via genuinely different proof technologies depending on the target statistic. - concept/random-subgraph-sampling — the core technique: fixed-probability random subgraph + union bound over two complementary bad events (clique survival vs. hidden-high-chromatic independent set), the reusable engine of this proof. - concept/color-critical-subgraph-mindegree — the classical fact (any $k$-chromatic-critical graph has min degree $\ge k-1$) that converts "independent in $H$" into "a union-bound-controllable dense edge set," the hinge of Step 2/event (2). - concept/ramsey-numbers — Erdős's 1947 probabilistic lower bound for diagonal Ramsey numbers $R(k,k)\ge 2^{k/2}$, invoked both for the boundary case in Lemma 2.1 and as the conceptual ancestor of the clique-suppression union bound in Lemma 2.2, event (1). - concept/probabilistic-deletion-construction — closely related but distinct probabilistic-method flavor (used e.g. for hypergraph Ramsey lower-bound constructions, see erdos/564.md); this problem's technique is the "two-sided union bound on a single random subgraph" variant of the same broad family.