TY - JOUR

T1 - Pure Pairs. V. Excluding Some Long Subdivision

AU - Scott, Alex

AU - Seymour, Paul

AU - Spirkl, Sophie

N1 - Publisher Copyright:
© 2023, The Author(s), under exclusive licence to János Bolyai Mathematical Society and Springer-Verlag GmbH Germany, part of Springer Nature.

PY - 2023/6

Y1 - 2023/6

N2 - A “pure pair” in a graph G is a pair A, B of disjoint subsets of V(G) such that A is complete or anticomplete to B. Jacob Fox showed that for all ε> 0 , there is a comparability graph G with n vertices, where n is large, in which there is no pure pair A, B with | A| , | B| ≥ εn . He also proved that for all c> 0 there exists ε> 0 such that for every comparability graph G with n> 1 vertices, there is a pure pair A, B with | A| , | B| ≥ εn1-c ; and conjectured that the same holds for every perfect graph G. We prove this conjecture and strengthen it in several ways. In particular, we show that for all c> 0 , and all ℓ1, ℓ2≥ 4 / c+ 9 , there exists ε> 0 such that, if G is an (n> 1) -vertex graph with no hole of length exactly ℓ1 and no antihole of length exactly ℓ2 , then there is a pure pair A, B in G with | A| ≥ εn and | B| ≥ εn1-c . This is further strengthened, replacing excluding a hole by excluding some “long” subdivision of a general graph.

AB - A “pure pair” in a graph G is a pair A, B of disjoint subsets of V(G) such that A is complete or anticomplete to B. Jacob Fox showed that for all ε> 0 , there is a comparability graph G with n vertices, where n is large, in which there is no pure pair A, B with | A| , | B| ≥ εn . He also proved that for all c> 0 there exists ε> 0 such that for every comparability graph G with n> 1 vertices, there is a pure pair A, B with | A| , | B| ≥ εn1-c ; and conjectured that the same holds for every perfect graph G. We prove this conjecture and strengthen it in several ways. In particular, we show that for all c> 0 , and all ℓ1, ℓ2≥ 4 / c+ 9 , there exists ε> 0 such that, if G is an (n> 1) -vertex graph with no hole of length exactly ℓ1 and no antihole of length exactly ℓ2 , then there is a pure pair A, B in G with | A| ≥ εn and | B| ≥ εn1-c . This is further strengthened, replacing excluding a hole by excluding some “long” subdivision of a general graph.

UR - http://www.scopus.com/inward/record.url?scp=85161966646&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85161966646&partnerID=8YFLogxK

U2 - 10.1007/s00493-023-00025-8

DO - 10.1007/s00493-023-00025-8

M3 - Article

AN - SCOPUS:85161966646

SN - 0209-9683

VL - 43

SP - 571

EP - 593

JO - Combinatorica

JF - Combinatorica

IS - 3

ER -