Linear anticomplete pairs in sparse H-free graphs

Conjecture 1.4 · arXiv:1810.00058

arXiv Conjecture high confidence— first stated 2020-12-07

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

Status partial high confidence

Conjecture 1.4 from arXiv:1810.00058 remains open in full generality. Partial progress has been made: Fox, Nguyen, Scott, and Seymour (arXiv:2307.00801) proved the conjecture for H=P4 with the optimal bound δ=ε, and more generally for all graphs H obtainable by vertex-substitution from copies of P4 and its subgraphs, via the stronger 'viral' property. Separately, Bucić, Fox, and Pham (arXiv:2403.08303) proved that the polynomial Rödl conjecture (Conjecture 1.3 in the source paper, which is equivalent to Conjecture 1.4 over all H by Rödl's theorem) is equivalent to the Erdős-Hajnal conjecture, establishing that the full resolution of Conjecture 1.4 is as hard as settling Erdős-Hajnal.

Cited literature (3)

partial Induced subgraph density. II. Sparse and dense sets in cographs (2023)

Jacob Fox, Tung Nguyen, Alex Scott, Paul Seymour · arXiv preprint · arXiv:2307.00801

Proves Conjecture 1.4 for H=P4 with the optimal bound δ=ε, and more generally for all graphs H obtainable by vertex-substitution from P4 and its subgraphs, via the 'viral' property.
reduction 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 (equivalent to Conjecture 1.4 for all H via Rödl's theorem) is equivalent to the Erdős-Hajnal conjecture; deduces that string graphs satisfy the polynomial Rödl conjecture.
partial Induced subgraph density. IV. New graphs with the Erdős-Hajnal property (2023)

Tung Nguyen, Alex Scott, Paul Seymour · arXiv preprint · arXiv:2307.06455

Establishes the Erdős-Hajnal property for infinitely many new graph classes, implicitly verifying Conjecture 1.4 for those classes via the equivalence proved by Bucić, Fox, and Pham.

Reviewer notes. Conjecture 1.4 is equivalent to Conjecture 1.3 (pure pairs) for all H simultaneously, by Rödl's theorem. Conjecture 1.3 in turn is now known to be equivalent to the Erdős-Hajnal conjecture (arXiv:2403.08303), so full resolution of Conjecture 1.4 is tied to one of the most prominent open problems in extremal graph theory. Partial results verified for P4-substitution families. The paper arXiv:2301.10147 takes a different approach via blockades and leaves this conjecture open.

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

Conjecture. For every graph $H$ there exists $\varepsilon > 0$ such that in every $H$-free $\varepsilon$-bounded graph $G$ with $|G| > 1$ vertices, there is an anticomplete $(\varepsilon|G|, \varepsilon|G|)$-pair.

Context

A graph $G$ is $\varepsilon$-bounded if its maximum degree is less than $\varepsilon|G|$. By a theorem of Rödl, $H$ satisfies Conjecture 1.3 if and only if both $H$ and $\bar{H}$ satisfy Conjecture 1.4, so the two conjectures are equivalent over all $H$. For certain graphs $H$, however, 1.4 is more tractable than 1.3.

Notes. PDF source — math may be garbled; the paper proves this for all almost-bipartite $H$ as Theorem 1.5

Source paper

Sparse graphs with no polynomial-sized anticomplete pairs
Maria Chudnovsky, Jacob Fox, Alex Scott, Paul Seymour, Sophie Spirkl · 2020-12-07
https://arxiv.org/abs/1810.00058 PDF source