Sparse pairs in H-free ε-bounded graphs

Status partial medium confidence

Conjecture 3.4 from arXiv:1810.00058, asserting the existence of c-sparse pairs in H-free ε-bounded graphs with quantitative polynomial bounds, remains open in general. Partial progress was made in arXiv:2307.00801 (Fox, Nguyen, Scott, Seymour), which proves the conjecture for H = P_4 with the optimal parameter and more generally for all graphs obtainable by vertex-substitution from P_4 and its subgraphs. The parent Conjecture 3.3 (which implies 3.4) was shown by Bucić, Fox, and Pham (arXiv:2403.08303) to be equivalent to the Erdős–Hajnal conjecture, placing Conjecture 3.4 in the broader landscape of open Ramsey-type problems.

Cited literature (2)

• partial Induced subgraph density. II. Sparse and dense sets in cographs (2024)
  Jacob Fox, Tung Nguyen, Alex Scott, Paul Seymour · arXiv preprint · arXiv:2307.00801

  Proves Conjecture 3.4 for H = P_4 with the optimal parameter δ = ε and a stronger maximum-degree bound, and more generally for all graphs H obtainable by vertex-substitution from copies of P_4 and its subgraphs, via the stronger '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 (Conjecture 3.3 in 1810.00058, which implies Conjecture 3.4) is equivalent to the Erdős–Hajnal conjecture; as a corollary deduces that string graphs satisfy the polynomial Rödl conjecture.

Reviewer notes. Conjecture 3.4 is the ε-bounded specialization of Conjecture 3.3; the implication chain 3.3 ⟹ 3.4 ⟹ Conjecture 1.4 holds. Progress on 3.4 comes primarily through the 'Induced subgraph density' series; 2307.00801 gives the strongest direct partial result (cograph/P_4 case). The full conjecture for general H remains open.

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