Linear pure pair in sparse H-free graphs

Possibility 1.6 · arXiv:2201.04062

arXiv Question high confidence— first stated 2023-10-29

Authors: Alex Scott, Paul Seymour, Sophie Spirkl

Status open high confidence

Possibility 1.6 asks whether the polynomial pure-pair bound in Theorem 1.4 can be strengthened so that one of the two sets always has linear size, for every graph H with sufficiently small congestion. The source paper's authors explicitly state they were unable to decide this, and the inductive proof technique cannot be directly extended. No subsequent paper resolving or substantially advancing the full conjecture was found in the indexed literature as of May 2026.

Reviewer notes. Both internal references are false positives — neither addresses Possibility 1.6 or the congestion parameter from Pure pairs VIII. A potentially related paper arXiv:2504.21127 ('On polynomially high-chromatic pure pairs') was found but its abstract concerns forest-free graphs and the polynomial Gyárfás-Sumner conjecture, not the specific claim about congestion and linear-vs-polynomial set sizes. No follow-up resolving Possibility 1.6 was found within the 5-call cap.

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

Question. For all $c > 0$, there exists $\xi > 0$ with the following property. For every graph $H$ with congestion at most $\xi$, there exists $\varepsilon > 0$ such that for every graph $G$ with $|G| > 1$ that is $H$-free and $\bar{H}$-free, there is a pure pair $A, B$ in $G$ with $|A| \geq \varepsilon|G|$ and $|B| \geq \varepsilon|G|^{1-c}$.

Context

Theorem 1.3 (from an earlier paper) gives a pure pair where one set has linear size, and the authors ask whether an analogous strengthening of their main result 1.4 holds: can one of the two sets always be taken to have linear size rather than polynomial size $\varepsilon|G|^{1-c}$? The authors explicitly state they were unable to decide this. The proof technique for 1.4 cannot be directly extended to resolve 1.6 because a key inductive argument requires strictly increasing shrinkage parameters, leaving no room for the stronger conclusion.

Notes. PDF source — labeled 'Possibility' rather than 'Conjecture' or 'Question' in the paper; math in 1.6 is readable but the congestion bound $c/(9+15c)$ in the nearby Theorem 1.4 appears garbled in the PDF extraction.

Source paper

Pure pairs. VIII. Excluding a sparse graph
Alex Scott, Paul Seymour, Sophie Spirkl · 2023-10-29
https://arxiv.org/abs/2201.04062 PDF source