Polynomial pure pairs for ordered graphs H
Informal: which graphs H admit polynomial-size pure pairs · arXiv:2111.00532
Status open high confidence
The question of which ordered graphs H yield polynomial-size pure pairs (|X|,|Y| >= epsilon W^c for fixed c>0) when excluding ordered B-transversal copies in a blockade of width W remains open in its general form. The source paper (Pure pairs IX) itself provides partial answers for trees and caterpillars, but the full characterisation is not resolved. Searches across the Pure pairs series (which runs through Pure pairs X, on tournaments) and recent literature found no follow-up paper directly settling this question.
Reviewer notes. No follow-up found. The Pure pairs series continues to Pure pairs X (arXiv not retrieved; published European J. Combinatorics 2023, about tournaments and the strong Erdos-Hajnal property), which does not address the polynomial-size question for the blockade/transversal setting. A related but distinct body of work on 'polynomially high-chromatic pure pairs' (Nguyen, arXiv:2504.21127, superseded by arXiv:2512.24907) concerns the chromatic Gyarfas-Sumner setting, not the ordered-graph blockade setting of this conjecture. The conjecture is recent (posted 2021, published 2024) and the absence of follow-up is expected.
Context
Immediately after stating Theorem 1.2 (Erdős–Hajnal–Pach), the authors ask for which $H$ the pure pair conclusion can be made polynomial in $W$. They note that $c = 1$ (linear pure pairs) is achievable only for $|H| \leq 2$, and flag the polynomial question as 'more promising'. The bulk of the paper provides partial answers for trees and caterpillars.
Notes. PDF source — the exact threshold formulas around this informal question may be partially garbled; overall intent is clear from context.
Source paper
Pure pairs. IX. Transversal trees
Alex Scott, Paul Seymour, Sophie Spirkl · 2024-02-06
https://arxiv.org/abs/2111.00532
PDF source