Pure Pairs. V. Excluding Some Long Subdivision

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| ≥ εn^1-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 ℓ₁, ℓ₂≥ 4 / c+ 9 , there exists ε> 0 such that, if G is an (n> 1) -vertex graph with no hole of length exactly ℓ₁ and no antihole of length exactly ℓ₂ , then there is a pure pair A, B in G with | A| ≥ εn and | B| ≥ εn^1-c . This is further strengthened, replacing excluding a hole by excluding some “long” subdivision of a general graph.