The Erdős-Hajnal High-Girth Subgraph Conjecture Holds in the Polynomial Chromatic-Sparsity Regime

Abstract

For a graph $G$ put $h_r(G)=\max \ddot{I}‡(H):H\subseteq G,\mathrm{girth}(H)\ge r.$ Erdős and Hajnal asked whether $h_r(G)\to \infty$ as $\ddot{I}‡(G)\to \infty$, for every fixed $r\ge 4$. We prove this in every fixed polynomial edge-density regime: for all $r\ge 4$, $k\ge 2$, $P,C>0$, there is $M=M_{r,k}(P,C)$ such that $\ddot{I}‡(G)\ge M,e(G)\le C\ddot{I}‡(G{)}^P⟹h_r(G)\ge k.$ Quantitatively, after replacing $P$ by $P\vee 2$ and $C$ by $C\vee 2$, $M_{r,k}(P,C)\le \exp !\left(O_{r,k}((P+2+\log (C\vee 2){)}^2)\right),$ and consequently the same conclusion holds throughout the quasi-polynomial range $e(G)\le \exp (C_0(\log \ddot{I}‡(G){)}^a),1<a<3/2,$ for all sufficiently large $\ddot{I}‡(G)$. In each fixed polynomial-density regime we also obtain $f_{P,C}(k,r)\le k^{O_{r,P,C}(1)}.$ The proof combines a chromatic-defect random extraction lemma, compact and near-quadratic sparse-core bases, and a peeling/thinning bootstrap increasing the admissible edge exponent by $1/(r-1)$. We also prove structural saturation results for possible counterexamples, including Moore-strength exact-cycle packings and quadratic saturation in projected colour-pair space. Finally, writing $h_r^{\mathrm{f}}(G)=\max \ddot{I}{‡}_{\mathrm{f}}(H):H\subseteq G,\mathrm{girth}(H)\ge r,$ we develop a fractional random-extraction framework based on Mohar-Wu preservation. We prove sufficient cheap-cycle-killing criteria and verify them for several structured families, including clique-organised families, line graphs of incidence graphs of equal-order generalized quadrangles and generalized hexagons, and the Bohman-Keevash tracking-time triangle-free-process graph. We also isolate a density-free obstruction that any proof using this fractional surgery route must overcome.

51 pages