Polynomial close Rödl property for hereditary families

Conjecture 10 · arXiv:2403.08303

arXiv Conjecture high confidence— first stated 2024-04-19

Authors: Matija Bucić, Jacob Fox, Huy Tuan Pham

Status open high confidence

Conjecture 10 asserts that every proper hereditary family has the 'polynomial close Rödl property': graphs merely close to the family (not necessarily in it) still contain large homogeneous sets. By Theorem 11 of the same paper, this property is equivalent to the Erdős-Hajnal property, so Conjecture 10 is in effect a reformulation of the Erdős-Hajnal conjecture for hereditary families, which remains wide open. No follow-up paper resolving Conjecture 10 in full generality was found in the indexed literature.

Reviewer notes. Conjecture 10 is equivalent to the Erdős-Hajnal conjecture via Theorem 11 of arXiv:2403.08303, making it as hard as one of the central open problems in extremal graph theory. Partial progress on the EH conjecture for specific graph classes (e.g., new prime graphs in 2307.06455) implicitly verifies Conjecture 10 for those classes via that equivalence, but the full conjecture remains open.

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

Conjecture. For each proper hereditary family $\mathcal{F}$ of graphs there are $C_{\mathcal{F}},d_{\mathcal{F}}>0$ such that if $0<\varepsilon<1/2$, every graph on $n$ vertices which is $\varepsilon^{d_{\mathcal{F}}}$-close to $\mathcal{F}$ contains an $\varepsilon$-homogeneous set of size at least $\varepsilon^{C_{\mathcal{F}}}n$.

Context

A graph on $n$ vertices is $\alpha$-close to a family $\mathcal{F}$ if one can add or delete at most $\alpha n^2/2$ edges to obtain a graph in $\mathcal{F}$. This conjecture, introduced as a natural extension for hereditary families, defines the polynomial close Rödl property; a family with this property also has the polynomial Rödl property.

Source paper

Equivalence between Erdős-Hajnal and polynomial Rödl and Nikiforov conjectures
Matija Bucić, Jacob Fox, Huy Tuan Pham · 2024-04-19
https://arxiv.org/abs/2403.08303