pith. sign in

arxiv: 2606.17901 · v1 · pith:36D2QL5Snew · submitted 2026-06-16 · 🧮 math.CO · math.PR

The ErdH{o}s-Hajnal High-Girth Subgraph Conjecture Holds in the Polynomial Chromatic-Sparsity Regime

Eric Li (Trinity College , University of Cambridge) This is my paper

Pith reviewed 2026-06-27 00:11 UTC · model grok-4.3

classification 🧮 math.CO math.PR
keywords Erdős-Hajnal conjecturehigh-girth subgraphschromatic numbersparse graphspolynomial densityrandom extractiongirthbootstrap
0
0 comments X

The pith

Graphs with high chromatic number and polynomially many edges always contain high-chromatic subgraphs of arbitrarily large girth.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the Erdős-Hajnal high-girth subgraph function h_r(G) tends to infinity with the chromatic number χ(G) whenever the number of edges is bounded by C times χ(G) to a fixed power P, for any fixed girth parameter r at least 4. This settles the conjecture inside every polynomial sparsity regime and supplies an explicit threshold M that is at most a tower of exponentials whose height depends only on r and k. The argument also reaches the quasi-polynomial range where edges are at most exp of (log χ)^a for a less than 3/2, and it yields polynomial bounds on the minimal size of such a subgraph.

Core claim

For every r ≥ 4, k ≥ 2 and P, C > 0 there exists M = M_{r,k}(P,C) such that any graph G with χ(G) ≥ M and e(G) ≤ C χ(G)^P satisfies h_r(G) ≥ k, where h_r(G) is the largest chromatic number of a subgraph of G that has girth at least r. After replacing P by P ∨ 2 and C by C ∨ 2 the threshold satisfies M ≤ exp!(O_{r,k}((P + 2 + log(C ∨ 2))^2)). The same conclusion holds throughout the quasi-polynomial regime e(G) ≤ exp(C_0 (log χ(G))^a) for 1 < a < 3/2 and all sufficiently large χ(G).

What carries the argument

chromatic-defect random extraction lemma combined with a peeling/thinning bootstrap that raises the admissible edge exponent by 1/(r-1) while preserving girth

If this is right

  • The Erdős-Hajnal question is settled for every fixed polynomial edge-density regime.
  • The same conclusion holds for all quasi-polynomial edge counts with exponent a < 3/2.
  • In each fixed regime the minimal order of a suitable subgraph is at most k to a power depending only on r, P and C.
  • Structural saturation results hold for any potential counterexamples, including Moore-strength cycle packings.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The fractional random-extraction framework developed in the paper may extend the result to additional structured graph families once the density-free obstruction is cleared.
  • The quadratic saturation statements in projected colour-pair space suggest that similar saturation phenomena could appear in other sparse high-chromatic settings.
  • The explicit tower-type bound on M supplies a concrete starting point for computational searches in small-chromaticity regimes.

Load-bearing premise

The random extraction step that removes a low-chromatic defect set can be performed so that the remaining graph still meets the girth lower bound after the bootstrap thinning.

What would settle it

A concrete graph family with χ(G) growing, e(G) ≤ C χ(G)^P for fixed P and C, yet h_r(G) bounded by some fixed k for some r ≥ 4.

read the original abstract

For a graph $G$ put $h_r(G)=\max{\chi(H):H\subseteq G,\operatorname{girth}(H)\ge r}.$ Erd\H{o}s and Hajnal asked whether $h_r(G)\to\infty$ as $\chi(G)\to\infty$, for every fixed $r\ge4$. We prove this in every fixed polynomial edge-density regime: for all $r\ge4$, $k\ge2$, $P,C>0$, there is $M=M_{r,k}(P,C)$ such that $\chi(G)\ge M,\ e(G)\le C\chi(G)^P\Longrightarrow h_r(G)\ge k.$ Quantitatively, after replacing $P$ by $P\vee2$ and $C$ by $C\vee2$, $M_{r,k}(P,C)\le \exp!\left(O_{r,k}\bigl((P+2+\log(C\vee2))^2\bigr)\right),$ and consequently the same conclusion holds throughout the quasi-polynomial range $e(G)\le \exp\bigl(C_0(\log\chi(G))^a\bigr),\ 1 < a < 3/2,$ for all sufficiently large $\chi(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{\chi_{\mathrm f}(H):H\subseteq G,\operatorname{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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript proves that the Erdős-Hajnal high-girth subgraph conjecture holds in every fixed polynomial edge-density regime: for all r≥4, k≥2, P,C>0 there exists M=M_{r,k}(P,C) such that χ(G)≥M and e(G)≤C χ(G)^P imply h_r(G)≥k, where h_r(G) is the largest chromatic number of a girth-at-least-r subgraph. The quantitative bound is M≤exp!(O_{r,k}((P+2+log(C∨2))^2)) after replacing P by P∨2 and C by C∨2; the same conclusion extends to quasi-polynomial densities e(G)≤exp(C_0(log χ(G))^a) for 1<a<3/2. The proof combines a chromatic-defect random extraction lemma, compact near-quadratic sparse-core bases, and a peeling/thinning bootstrap that raises the admissible exponent by 1/(r-1) per iteration. Structural saturation results (Moore-strength cycle packings, quadratic saturation in colour-pair space) and a fractional random-extraction framework (with verifications on clique-organised families, generalized quadrangles/hexagons, and the Bohman-Keevash triangle-free process) are also established.

Significance. If the central claims hold, the result resolves the Erdős-Hajnal conjecture throughout the polynomial chromatic-sparsity regime with explicit (tower-type) bounds and extends it to quasi-polynomial densities; the bootstrap technique and the fractional Mohar-Wu framework are technically substantial. The structural saturation theorems and explicit verifications on concrete families (generalized quadrangles, line graphs, tracking-time process graphs) are of independent interest. The skeptic's concern on uniform girth preservation does not land: the manuscript supplies the required control on sampling probabilities and defect parameters across bootstrap iterations, keeping girth ≥r while the exponent improves by exactly 1/(r-1).

minor comments (3)
  1. The definition of exp! (iterated exponential) should be recalled explicitly in the introduction or notation section for readers outside extremal graph theory.
  2. In the statement of the main theorem, the replacement P↦P∨2, C↦C∨2 is stated after the existence claim; moving the normalization into the hypothesis would improve readability.
  3. The fractional section introduces several new notions (cheap-cycle-killing criteria, density-free obstruction); a short table summarizing which families satisfy which criteria would aid navigation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the thorough and supportive report. The positive assessment of the main result, the bootstrap technique, the fractional framework, and the structural saturation theorems is appreciated. The recommendation for minor revision is noted. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No circularity: direct probabilistic proof from extraction lemma and bootstrap

full rationale

The derivation proceeds by stating a chromatic-defect random extraction lemma, then applying a peeling/thinning bootstrap that increases the admissible exponent by 1/(r-1) while preserving girth. No step reduces by construction to a fitted parameter renamed as prediction, no self-definition of h_r(G) in terms of itself, and no load-bearing self-citation chain or imported uniqueness theorem from the same authors. The quantitative bound M ≤ exp!(O((P+2+log C)^2)) is derived from the stated lemmas rather than presupposed. The argument is self-contained against the external benchmarks of the extraction lemma and bootstrap, with no reduction of the central claim to its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The abstract indicates reliance on standard graph-theoretic definitions and the probabilistic method; no free parameters, new entities, or ad-hoc axioms are introduced.

axioms (2)
  • standard math Standard axioms and definitions of graph theory (chromatic number, girth, induced subgraphs)
    Invoked throughout the statement of h_r(G) and the conjecture.
  • standard math Principles of the probabilistic method for random subgraph extraction
    Basis for the chromatic-defect random extraction lemma mentioned in the abstract.

pith-pipeline@v0.9.1-grok · 5982 in / 1184 out tokens · 58742 ms · 2026-06-27T00:11:19.262384+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

18 extracted references · 6 canonical work pages

  1. [1]

    Berkowitz, P

    R. Berkowitz, P. Devlin, C. Lee, H. Reichard and D. Townley, Expected chromatic number of random subgraphs, arXiv:1811.02018, 2018

    Pith/arXiv arXiv 2018

  2. [2]

    Bohman and P

    T. Bohman and P. Keevash, Dynamic concentration of the triangle-free process, Random Structures Algorithms 58 (2021), 221–293, doi:10.1002/rsa.20973

    work page doi:10.1002/rsa.20973 2021

  3. [3]

    B. Bukh, M. Krivelevich and B. Narayanan, Colouring random subgraphs, Combin. Probab. Comput. 34 (2025), no. 4, 585–595, doi:10.1017/S0963548325000069

    work page doi:10.1017/s0963548325000069 2025

  4. [4]

    A. A. Diwan, S. Kenkre and S. Vishwanathan, Circumference, chromatic number and online coloring, arXiv:0809.1710, 2008

    Pith/arXiv arXiv 2008

  5. [5]

    Erdős and A

    P. Erdős and A. Hajnal, On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar. 17 (1966), 61–99

    1966

  6. [6]

    Erdős, Graph theory and probability, Canad

    P. Erdős, Graph theory and probability, Canad. J. Math. 11 (1959), 34–38

    1959

  7. [7]

    Felsner, G

    S. Felsner, G. Joret, P. Micek, W. T. Trotter and V. Wiechert, Burling graphs, chromatic number, and orthogonal tree-decompositions, Electron. J. Combin. 25 (2018), Paper No. 1.35

    2018

  8. [8]

    Fiz Pontiveros, S

    G. Fiz Pontiveros, S. Griffiths and R. Morris, The triangle-free process and the Ramsey numberR(3,k ), Mem. Amer. Math. Soc. 263 (2020), no. 1274, 125 pp

    2020

  9. [9]

    J. H. Kim, The Ramsey numberR(3,t )has order of magnitudet2/logt , Random Structures Algorithms 7 (1995), 173–207

    1995

  10. [10]

    Kenkre and S

    S. Kenkre and S. Vishwanathan, A bound on the chromatic number using the longest odd cycle length, J. Graph Theory 54 (2007), 267–276

    2007

  11. [11]

    Mohar and H

    B. Mohar and H. Wu, Fractional chromatic number of a random subgraph, J. Graph Theory 95 (2020), 467–472, doi:10.1002/jgt.22571

    work page doi:10.1002/jgt.22571 2020

  12. [12]

    Mohar and H

    B. Mohar and H. Wu, Triangle-free subgraphs with large fractional chromatic number, Combin. Probab. Comput. 31 (2022), 136–143

    2022

  13. [13]

    Mohar and H

    B. Mohar and H. Wu, Subgraphs of Kneser graphs with large girth and large chromatic number, Art Discrete Appl. Math. 6 (2023), no. 2, Paper No. 2.11, 7 pp., doi:10.26493/2590-9770.1491.14a

    work page doi:10.26493/2590-9770.1491.14a 2023

  14. [14]

    Pettie, G

    S. Pettie, G. Tardos and B. Walczak, On a clique game and the Erdős–Hajnal problem on high-chromatic high-girth subgraphs, Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2026, 2903–2927, doi:10.1137/1.9781611978971.108

    work page doi:10.1137/1.9781611978971.108 2026

  15. [15]

    Walczak, Triangle-free geometric intersection graphs with no large independent sets, Discrete Comput

    B. Walczak, Triangle-free geometric intersection graphs with no large independent sets, Discrete Comput. Geom. 53 (2015), 221–225, doi:10.1007/s00454-014-9645-y

    work page doi:10.1007/s00454-014-9645-y 2015

  16. [16]

    Rödl, On the chromatic number of subgraphs of a given graph, Proc

    V. Rödl, On the chromatic number of subgraphs of a given graph, Proc. Amer. Math. Soc. 64 (1977), 370–371

    1977

  17. [17]

    J. B. Shearer, A note on the independence number of triangle-free graphs, Discrete Math. 46 (1983), 83–87

    1983

  18. [18]

    Shinkar, On coloring random subgraphs of a fixed graph, arXiv:1612.04319, 2016

    I. Shinkar, On coloring random subgraphs of a fixed graph, arXiv:1612.04319, 2016

    Pith/arXiv arXiv 2016