Chromatic-defect random extraction + sparse-core bootstrapping (the Erdős–Hajnal high-girth subgraph technique)

Statement

The technique in one sentence. To force a subgraph of prescribed girth $\ge r$ and prescribed chromatic number $\ge k$ out of a graph $G$ that is only *polynomially* dense in its own chromatic number ($e(G)\le C\chi(G)^P$, not the unrestricted density Erdős's 1959 argument needs), replace "chromatic number" as the quantity being preserved by a strictly more robust surrogate — the chromatic defect $\mu_q(G)$, the minimum number of monochromatic edges over all $q$-colourings — because $\mu_q(G)$ is large ($\gg m^2/q$) *purely as a consequence of* $\chi(G)=m$ being large, with no reference to density; then run the classical alteration recipe (random-thin the edges, delete one edge per surviving short cycle) *on the defect* instead of on the chromatic number directly, so the deletion budget only has to beat the expected number of short cycles, not the whole edge count; and when a single random thinning isn't enough because the graph is too sparse for the required probability $p$ to make both the defect-survival event and the low-cycle-count event simultaneously likely, bootstrap: peel off the high-degree vertices into a denser piece $Z$ (recurse there on a smaller *vertex* exponent) and, on the remaining bounded-degree piece $R$, either find a genuinely sparse ($\ll t^\gamma$-edge) monochromatic-edge subgraph directly satisfying the base case, or apply random thinning at a rate that increases the admissible edge exponent by exactly $1/(r-1)$ per bootstrap step — iterating this finitely many times from a near-quadratic base case reaches *every* fixed polynomial density regime $e(G)\le C\chi(G)^P$.

Core object — the $q$-colour chromatic defect (Section 2, Def. + Lemma 2.1, read in full). For $q\ge1$ and a graph $G$, $$ \mu_q(G) \;=\; \min_{\psi:V(G)\to[q]} \bigl|\{uv\in E(G):\psi(u)=\psi(v)\}\bigr|, $$ the minimum number of monochromatic edges over *all* $q$-colourings (not just proper ones) — so $G$ is $q$-colourable iff $\mu_q(G)=0$. Lemma 2.1 (Chromatic defect). For every $G$ with $\chi(G)=m$ and every $q\ge1$, $\mu_q(G)\ge D_q(m)$ (an exact "balanced-partition" quantity), and in particular, whenever $m\ge q$, $$ \mu_q(G) \;\ge\; \frac{(m-q)^2}{2q}. $$ *Proof idea*: any $\psi:V(G)\to[q]$ splits $G$ into $q$ induced pieces of chromatic numbers $t_1,\dots,t_q$ summing to $\ge m$ (else $G$ itself would be colourable with fewer colours by concatenating palettes); each piece, being non-colourable below $t_i$, contains a $t_i$-critical subgraph with $\ge\binom{t_i}2$ edges, all $\psi$-monochromatic; minimizing $\sum\binom{t_i}2$ subject to $\sum t_i\ge m$ and applying Cauchy–Schwarz gives the bound. This is the load-bearing fact of the whole technique: a large chromatic number forces a large, purely combinatorial "monochromatic edge count" under any coarse recolouring, with zero density hypothesis.

Deletion criterion (Lemma 2.2, read in full). If the short-cycle transversal number $\tau_{<r}(G)$ (min. edges to delete to kill all cycles of length $<r$) is *strictly less than* $\mu_q(G)$, then $h_r(G)\ge q+1$, where $h_r(G):=\max\{\chi(H):H\subseteq G,\ \mathrm{girth}(H)\ge r\}$. *Proof*: take a minimum short-cycle transversal $F$ and set $G'=G-F$; if $\chi(G')\le q$ its optimal colouring witnesses $\mu_q(G)\le|F|<\mu_q(G)$, a contradiction, so $\chi(G')\ge q+1$ while $\mathrm{girth}(G')\ge r$ by construction. This is the entire mechanism in one line: beat the short-cycle count with the defect, and deleting one edge per short cycle simultaneously kills all short cycles while (by the defect bound) leaving every $q$-colouring still imperfect.

Theorem 3.1 (Robust random extraction — the base engine). Fix $r\ge4$, $q\ge1$. Let $J$ have $n=|V(J)|$, $m=\chi(J)>q$, and put $M_q=(m-q)^2/(2q)$. If $p\in(0,1]$ satisfies $$ p M_q \;\ge\; 16\bigl(n\log q+\log 4\bigr) \qquad\text{(3.1)} $$ $$ \sum_{\ell=3}^{r-1} p^\ell C_\ell(J) \;\le\; \frac{pM_q}{16} \qquad\text{(3.2)} $$ (where $C_\ell(J)$ is the number of $\ell$-cycles in $J$), then $J$ contains a subgraph $H$ with $\mathrm{girth}(H)\ge r$ and $\chi(H)\ge q+1$. *Proof*: thin $J$'s edges independently at rate $p$ to get $J_p$; for each of the $q^n$ maps $\psi:V(J)\to[q]$, the surviving $\psi$-monochromatic edge count is $\mathrm{Bin}(N_\psi,p)$ with $N_\psi\ge M_q$, so Chernoff + union bound over all $q^n$ colourings (using (3.1)) gives, with probability $>3/4$, every $q$-colouring still has $\ge pM_q/2$ monochromatic edges surviving; independently, Markov's inequality on the expected short-cycle count (using (3.2)) gives, with probability $\ge3/4$, at most $pM_q/4$ short cycles survive. A union bound gives a single outcome with both properties; deleting one edge per surviving short cycle removes $<pM_q/4$ edges total, which cannot destroy every $q$-colouring's $\ge pM_q/2$ monochromatic edges — so the pruned graph has $\chi\ge q+1$ and girth $\ge r$.

Theorem 1.1 (Main theorem, polynomially sparse graphs). Fix $r\ge4$, $k\ge2$, $P,C>0$. There is $M=M(r,k,P,C)$ such that every graph $G$ with $\chi(G)\ge M$ and $e(G)\le C\chi(G)^P$ contains $H\subseteq G$ with $\mathrm{girth}(H)\ge r$, $\chi(H)\ge k$, with the quasipolynomial bound $M_{r,k}(P,C)\le\exp\bigl(O_{r,k}((P+2+\log(C\vee2))^2)\bigr)$; consequently the same conclusion extends to the quasi-polynomial density range $e(G)\le\exp(C_0(\log\chi(G))^a)$ for every $1<a<3/2$.

Bootstrap statement $\mathbf S(A)$ (Section 6). For real $A>0$: *for every $x<A$ and every $C>0$, there is $M$ such that $\chi(G)\ge M$, $e(G)\le C\chi(G)^x\Rightarrow h_r(G)\ge k$.* Two lemmas drive the whole induction:

- Lemma 6.1 (Base exponent). $\mathbf S(A_0)$ holds for $A_0=2+\tfrac{2}{3r-5}$ — an immediate corollary of the near-quadratic sparse-core theorem (Theorem 1.6: fix $\varepsilon<2/(3r-5)$; if $J\subseteq G$ has $\chi(J)=m\ge M$ and $e(J)\le Bm^{2+\varepsilon}$, then $G\supseteq H$ with $\mathrm{girth}(H)\ge r,\ \chi(H)\ge k$), itself proved from Theorem 3.1 after a spectral cycle-count bound $C_\ell(G)\le(2e)^{\ell/2}\,(\text{polynomial in } m)$ that makes conditions (3.1)/(3.2) simultaneously satisfiable when the edge count is only slightly super-quadratic in $m$. - Lemma 6.3 (Exponent increment). If $\mathbf S(A)$ holds then $\mathbf S(A+\tfrac1{r-1})$ holds. *Proof*: pass to an $m$-critical subgraph $G_0$ (so $|V(G_0)|\le C_1 m^{x-1}$, since minimum degree $\ge m-1$ forces $2e(G_0)\ge(m-1)|V(G_0)|$), giving simultaneous edge exponent $\bar x$ and vertex exponent $y=\bar x-1$; apply Proposition 6.2 (Mixed peeling and thinning), whose hypothesis $y<(r-1)A-(r-2)x$ is *exactly* what $x<A+1/(r-1)$ buys after the vertex-count conversion — this arithmetic identity is the entire reason the increment is $1/(r-1)$ and not some other constant.

Proposition 6.2, the peeling/thinning dichotomy (full mechanism). Given $\mathbf S(A)$, $x>A$, and a companion vertex-count exponent $y$ satisfying the slack condition, for $G$ with $\chi(G)=t$, $e(G)\le Ct^x$, $|V(G)|\le Ct^y$: 1. Peel high-degree vertices. Set threshold degree $t^d$ ($d=x-u+\eta$ for a small tuning parameter $\eta$), let $Z=\{v:\deg_G(v)>t^d\}$, $R=G-Z$. Since $e(G)\le Ct^x$, $|Z|\le 2Ct^{x-d}=2Ct^{u-\eta}$ — a smaller vertex exponent. 2. Dichotomy on $\chi(G[Z])$. If $\chi(G[Z])\ge t/2$, recurse: $Z$ itself has a smaller vertex exponent $u-\eta$, so the *inductive hypothesis on $u$* (a finite descent, terminating at a fixed compact exponent $\beta_*=1+1/(4r)$ where Theorem 1.5, the compact-core theorem, applies directly) gives $h_r(G[Z])\ge k$. Otherwise $\chi(R)>t/2$ and every vertex in $R$ has degree $\le t^d$ (bounded-degree piece). 3. Small-defect vs. random-thinning split on $R$. Either (a) *some* $q$-colouring $\psi$ of $R$ already has few ($\le t^\gamma$, $\gamma=A-\eta$) monochromatic edges — then the graph $M_\psi$ of those edges has $\chi(M_\psi)=s\ge t/(2q)$ (else combining $\psi$'s colour with an $s$-colouring of $M_\psi$ would properly colour $R$ with $<t/2$ colours) and edge-density exponent $\gamma<A$ measured in *its own* chromatic number $s$ — so the previous bootstrap level $\mathbf S(A)$ applies directly, closing the induction; or (b) *every* $q$-colouring of $R$ has $>t^\gamma$ monochromatic edges — then the chromatic-defect bound (Lemma 2.1, applied uniformly over all $q^{|V(R)|}$ colourings via Chernoff + union bound) is large enough at a random thinning probability $p=Lt^{u-\gamma}$ to guarantee, simultaneously, every $q$-colouring keeps enough monochromatic edges *and* (using $\Delta(R)\le t^d$ to bound $C_\ell(R)\le 2e(R)\Delta(R)^{\ell-2}$) few enough short cycles survive — exactly Theorem 3.1's random-extraction argument, run inside the bounded-degree piece $R$.

WHEN it applies. Whenever the target is "graph of chromatic number $\ge M$ and edge count $\le C\chi(G)^P$ (any fixed polynomial density regime) contains a high-girth, high-chromatic subgraph" — the specific Erdős–Hajnal high-girth conjecture — or, more generally, any setting where (a) chromatic number alone gives no density control, but (b) a *defect*-style quantity (monochromatic edges under a coarse recolouring) can be shown large purely from $\chi$ being large, and (c) the "bad" local structure to delete (here: short cycles) has an expected count controllable by Markov/Chernoff once edges are thinned at the right rate.

Facts

- **The underlying open problem is Erdős Problem erdos/108: "For every $r\ge4$ and $k\ge2$ is there some finite $f(k,r)$ such that every graph of chromatic number $\ge f(k,r)$ contains a subgraph of girth $\ge r$ and chromatic number $\ge k$?" (erdosproblems.com/108, attributed [Er71],[Er79b],[Er81], still listed OPEN as of Jan 2026, i.e. before this paper). This 2026 paper does not resolve #108 in full generality** — it resolves only the sub-family where a witnessing chromatic-critical core has edge count bounded by a *fixed polynomial* in its own chromatic number; graphs whose critical cores are super-polynomially dense (in their own $\chi$) remain outside its reach. - Rödl's 1977 theorem is the $r=4$ anchor case, proved decades earlier by an entirely different (non-quantitative) method: sufficiently high $\chi$ forces a triangle-free subgraph of large $\chi$ [V. Rödl, "On the chromatic number of subgraphs of a given graph," Proc. Amer. Math. Soc. 64 (1977), 370–371]. Li's paper explicitly frames its Theorem 1.1 as *not* subsuming Rödl's unconditional $r=4$ result (Rödl's has no density restriction) but as giving a quantitatively effective, uniform-in-$r$ machine that reaches every $r\ge4$ under a polynomial-density hypothesis. - Pettie–Tardos–Walczak's tower-type lower bounds (via Burling graphs, cited as [14]) show $f(k,5)$ must be enormous (tower-type in $k$) for the *unrestricted*-density $r=5$ case — this is the frontier case Corollary 1.2 addresses under the polynomial restriction, showing the sparse regime is dramatically better-behaved than the worst case the PTW examples witness. - The technique is a direct quantitative descendant of Erdős's classical 1959 alteration-method proof that high-girth, high-chromatic graphs exist unconditionally (no density constraint) — see The alteration (deletion) method — probabilistic existence proofs that build an almost-good random structure, then delete its blemishes; canonical instance: Erdős's 1959 high-girth/high-chromatic-number graphs. The 1959 proof uses $G(n,p)$ with $p=n^{\theta-1}$ and deletes one vertex per short cycle to control $\alpha(G)$ (hence $\chi$ via $\chi\ge n/\alpha$); the 2026 technique instead thins the *edges* of an already-given graph $G$ and deletes one edge per short cycle, replacing "control $\alpha(G)$" with "control $\mu_q(G)$" — the shift from *building* a random graph from scratch to *extracting* a sparse high-girth subgraph *from within* a fixed dense one is exactly why chromatic defect (which needs no global randomness assumption on $G$ itself) is the right load-bearing quantity. - The increment $1/(r-1)$ is not a heuristic constant — it falls out algebraically from matching Proposition 6.2's slack condition $y<(r-1)A-(r-2)x$ against the vertex-exponent-from-edge-exponent conversion $y=\bar x-1$ that critical subgraphs give for free (minimum degree $\ge m-1$ forces $|V|\lesssim e/m$); Lemma 6.3's proof is essentially solving this one inequality for the largest admissible increment. - Quantitative bound: $M_{r,k}(P,C)\le\exp(O_{r,k}((P+2+\log(C\vee2))^2))$ — quasipolynomial in $P$, not polynomial; the paper explicitly analyzes (§ on "limits of density reduction") why a natural one-parameter refinement of the peeling scheme (imbalanced splits) *cannot* beat the quadratic-in-$P$ exponent, i.e. the quadratic cost is closely tied to this particular bootstrap architecture, not merely un-optimized constants. - Classical base cases $k=2,3$ need none of this machinery: $k=2$ is trivial (any graph with an edge and enough vertices has $h_r\ge2$ once girth $\ge r$ is arrangeable), and $k=3$ follows directly from the Erdős–Hajnal odd-cycle theorem erdos/57-adjacent classical fact: a non-bipartite graph's longest odd cycle length $\ell$ bounds $\chi(G)\le\ell+1$ [Erdős–Hajnal 1966, Acta Math. Hungar. 17, 61–99], sharpened by Kenkre–Vishwanathan 2007. - A fractional-chromatic-number sibling framework is developed in the same paper (Section 9) via Mohar–Wu's fractional random-subgraph preservation theorem (order $\rho\chi_f(G)/\log\chi_f(G)$, no dependence on $|V(G)|$) — structurally analogous but bottlenecked by a different, "density-free cheap-cycle-killing" obstruction, verified only for structured families (clique-organised graphs, line graphs of incidence graphs of generalized quadrangles/hexagons, Bohman–Keevash triangle-free-process graphs).

Technique

WHY it works (the mechanism, for recombination). 1. Defect, not chromatic number, is the quantity that survives coarsening. $\chi(G)$ itself gives no leverage under a random edge deletion — you cannot directly bound how much thinning an edge-set can tolerate before $\chi$ drops. But $\mu_q(G)\ge(m-q)^2/(2q)$ (Lemma 2.1) converts "chromatic number is large" into "every possible $q$-colouring, however bad, has many monochromatic edges" — a *uniformly quantified* combinatorial surplus that a Chernoff bound (applied per-colouring, then unioned over all $q^n$ colourings) can show survives random thinning with high probability. This is the same "control a robust surrogate quantity, not the fragile target quantity directly" idea that appears whenever a direct probabilistic argument on $\chi$ itself is intractable. 2. The alteration step is unchanged in spirit from 1959, but the roles of "random object" and "thing being pruned" are swapped. Erdős 1959 builds $G(n,p)$ from scratch and prunes vertices to control $\alpha(G)$; here $G$ is *given* (with its density constraint), and edges are thinned, then one edge per surviving short cycle is deleted — this only works because $\mu_q$'s lower bound needs no density hypothesis on $G$ at all, so it applies to *any* input, however sparse. 3. The two Chernoff/Markov conditions (3.1)/(3.2) are in direct tension — (3.1) wants $p$ *large enough* to keep enough monochromatic edges (defect survives), (3.2) wants $p$ *small enough* to keep few enough short cycles (girth survives) — and Theorem 3.1's proof is exactly finding the window of $p$ where both hold simultaneously, which requires $M_q$ (the defect) to dominate the (density-dependent) cycle count $C_\ell(J)$ by a wide enough margin. This is why density matters: too many edges means too many short cycles for any single $p$ to kill without also destroying the defect. 4. When no single $p$ works (density too high for the base theorem), bootstrap by trading edges for a cheaper problem. High-degree vertices are peeled into $Z$, recursively handled at a *strictly smaller vertex-count exponent* (finite descent to a fixed compact-core base case, Theorem 1.5); the remaining bounded-degree piece $R$ is small enough (bounded max-degree controls the short-cycle count via $C_\ell(R)\le2e(R)\Delta(R)^{\ell-2}$) that *either* it already contains a genuinely low-density monochromatic-edge subgraph solvable by a previous, weaker density hypothesis $\mathbf S(A)$ (small-defect branch), *or* random thinning at a carefully tuned rate closes the argument directly (Theorem 3.1 again, now inside $R$). Each application of Lemma 6.3 buys exactly $1/(r-1)$ more edge-exponent headroom; finitely many iterations from the near-quadratic base ($A_0=2+2/(3r-5)$) reach any fixed target $P$. 5. The whole architecture is a two-level alteration method: an *outer* alteration (peel high-degree vertices, delete them from consideration) nested around an *inner* alteration (thin edges, delete short cycles) — with the outer level's job being purely to buy enough sparsity headroom for the inner level's Chernoff argument to close.

HOW to use it to prove things (recombination steps)

1. Identify the two competing structures: a chromatic-number lower bound you want to preserve (or force), and a "bad local substructure" (short cycles) whose count you want to drive to zero by deletion, in a setting where naive density is *too high* for a single random-thinning argument to control both simultaneously. 2. Find or construct a defect-type surrogate for the chromatic-number target: a quantity (like $\mu_q(G)$) that is provably large as a *pure* function of $\chi(G)$, with no density hypothesis, ideally via a clean extremal-graph fact (here: $t$-critical subgraphs have $\ge\binom t2$ edges) plus a convexity/Cauchy–Schwarz optimization over a balanced partition. 3. Set up the Chernoff-vs-Markov window: write down the two inequalities analogous to (3.1)/(3.2) — "the defect survives thinning at rate $p$ with high probability, union-bounded over all colourings" and "the expected bad-substructure count after thinning at rate $p$ is small enough" — and check whether a single $p$ satisfies both given your density hypothesis. If yes, you're in the base-case regime (compact-core / near-quadratic-core territory here). 4. If no single $p$ works, look for a peeling parameter. Split the vertex set by a degree threshold tuned to a free exponent $\eta$; show the high-degree part has a *strictly smaller* controlling parameter (vertex count here) enabling recursion, and confine the base random-thinning argument to the low-degree remainder, where a global density bound (max degree) controls the bad-substructure count more tightly. 5. Solve for the exact increment your bootstrap step buys by matching the slack inequalities that make the recursion consistent (here, $\sigma_\ell=\ell A-(\ell-1)x-y>0$ for all relevant $\ell$, minimized at the boundary $\ell=r-1$) against whatever "for free" relation your peeling step gives (here, criticality's $|V|\lesssim e/\chi$). The resulting increment is usually a clean rational function of the problem's discrete parameters (here $1/(r-1)$). 6. Iterate the bootstrap finitely many times from the base case to reach any fixed target parameter, and track the total constant/threshold blow-up explicitly if you want an effective (rather than merely existential) bound — the quasipolynomial-in-$P$ cost here traces directly to iterating a fixed-size loss at each of $\Theta(P)$ bootstrap steps.

What this technique does NOT give (limits, when to reach for something else)

- It does not resolve erdos/108 in full — only the polynomial- (and quasi-polynomial-, exponent $<3/2$) density regime; graphs whose minimal high-chromatic witnessing subgraphs are super-polynomially dense in their own chromatic number are untouched, and the paper explicitly notes a counterexample to the full conjecture (if one exists) must fail to have any polynomially-sparse high-chromatic critical core. - It gives a quasipolynomial, not polynomial, threshold $M_{r,k}(P,C)$ in the density exponent $P$, and the paper argues a natural refinement (imbalanced peeling splits) cannot improve this within the same architecture — a genuinely different idea would be needed for a near-linear-in-$P$ bound. - The fractional analogue $h_r^{\mathrm f}(G)$ is not resolved by this machinery; it is bottlenecked by a different, density-free "cheap-cycle-killing" obstruction (Section 9), verified only for specific structured families, not in general — see Mohar–Wu's fractional preservation theorem for the relevant sibling tool. - It is an existence result (some subgraph $H$ exists), not a construction or characterization of extremal examples; for lower-bound obstructions (how bad can $f(k,r)$ be), see the tower-type Pettie–Tardos–Walczak Burling-graph examples, a structurally unrelated technique.

Related

- erdos/108 — the general open Erdős–Hajnal high-girth subgraph conjecture (all $r,k$, no density restriction); this technique resolves exactly the polynomial- and quasi-polynomial-edge-density sub-family, leaving the unrestricted-density case open. - erdos/57 — the sibling odd-cycle/chromatic-number problem (Erdős–Hajnal 1966 conjecture, solved by Liu–Montgomery via sublinear expanders); its classical $k=3$ predecessor fact (odd-cycle length bounds $\chi$) is what this paper's $k=3$ base case reduces to directly, without needing the random-extraction machinery at all. - The alteration (deletion) method — probabilistic existence proofs that build an almost-good random structure, then delete its blemishes; canonical instance: Erdős's 1959 high-girth/high-chromatic-number graphs — the classical unrestricted-density 1959 Erdős predecessor (random graph $G(n,p)$ + delete-one-vertex-per-short-cycle to control $\alpha(G)$); this page's technique is the natural "extract from a given sparse graph instead of building from scratch" generalization, replacing $\alpha(G)$-control with chromatic-defect-control as the load-bearing preserved quantity. - Discharging method — charge-counting technique for planar/structural graph coloring and cycle-existence proofs — a structurally different "local⇄global" proof template (conserved charge redistribution) for forcing local structures in sparse/planar graphs; useful contrast to chromatic-defect random extraction's "randomized alteration" mechanism for a similar flavor of sparse-graph structural-forcing goal. - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the more elementary Chebyshev/variance-based concentration ancestor; this technique's Theorem 3.1 uses only Chernoff (for the defect-survival union bound) and Markov (for the cycle-count bound), not full second-moment machinery, reflecting that both target quantities here are sums of independent or near-independent indicator-like variables rather than requiring variance control.