Polynomial δ Dependence in Rödl's Theorem

Polynomial dependence of $\delta$ on $d$ in Rödl's theorem · arXiv:1803.03588

arXiv Informal medium confidence— first stated 2018-03-09

Authors: Maria Chudnovsky, Jacob Fox, Alex Scott, Paul Seymour, Sophie Spirkl

Status partial high confidence

The polynomial bound on $\delta$ in Rödl's theorem remains unproved for general $H$; the best known bound is the loglog improvement $\delta = 2^{-c(\log(1/d))^2/\log\log(1/d)}$ of Bucić–Nguyen–Scott–Seymour (2023), confirming the gap between the exponential status quo and the conjectured polynomial dependence. Notably, Bucić–Fox–Pham (2024) proved that the polynomial Rödl conjecture is in fact *equivalent* to the full Erdős–Hajnal conjecture (strengthening the mere implication stated in the source paper), and also verified the polynomial Rödl property for the special class of string graphs.

Cited literature (2)

partial Induced subgraph density. I. A loglog step towards Erdos-Hajnal (2023)

Matija Bucić, Tung Nguyen, Alex Scott, Paul Seymour · arXiv preprint · arXiv:2301.10147

Improves the exponent in Rödl's bound to $\delta = 2^{-c(\log(1/d))^2/\log\log(1/d)}$, a loglog gain over Fox–Sudakov, but does not achieve the conjectured polynomial dependence.
partial Equivalence between Erdős-Hajnal and polynomial Rödl and Nikiforov conjectures (2024)

Matija Bucić, Jacob Fox, Huy Tuan Pham · arXiv preprint · arXiv:2403.08303

Proves that the polynomial Rödl conjecture (and the polynomial Nikiforov conjecture) are each equivalent to the Erdős–Hajnal conjecture, upgrading the one-directional implication stated in the source paper to a full equivalence; also verifies the polynomial Rödl property for string graphs as a special case.

Reviewer notes. The conjecture as stated in the source paper has two components: (1) that polynomial δ holds in Rödl's theorem, and (2) that this implies Erdős–Hajnal. Component (2) was already known in 2018; arXiv:2403.08303 (2024) strengthens it to a full equivalence. Component (1) — the polynomial bound itself — remains open for general H, with the loglog bound of arXiv:2301.10147 being the current state of the art.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. A polynomial dependence of $\delta$ on $d$ holds in Theorem 2.2, i.e., the $\delta$ satisfying Rödl's theorem can be taken to be polynomial in $d$; and this would imply the Erdős-Hajnal conjecture itself.

Context

In the discussion following Rödl's theorem (2.2), the authors note that Rödl's original proof gives a tower-type bound for $1/\delta$ in terms of $1/d$, while Fox and Sudakov [7] improve this to $\delta = 2^{-|V(H)|^{15}(\log(1/d))^2}$. A polynomial dependence is stated as a community conjecture whose truth would imply the full Erdős-Hajnal conjecture.

Notes. Stated in passive voice ('It is conjectured that…') without a specific citation; appears to be a community/folklore conjecture presented without explicit attribution. For $H = C_5$ the authors note one can achieve the intermediate bound $\delta = 2^{-O((\log(1/d))^2 / \log\log(1/d))}$.

Source paper

Towards Erdos-Hajnal for graphs with no 5-hole
Maria Chudnovsky, Jacob Fox, Alex Scott, Paul Seymour, Sophie Spirkl · 2018-03-09
https://arxiv.org/abs/1803.03588 PDF source