Pure Pairs. VIII. Excluding a Sparse Graph

A pure pair of size t in a graph G is a pair A, B of disjoint subsets of V(G), each of cardinality at least t, such that A is either complete or anticomplete to B. It is known that, for every forest H, every graph on \(n\ge 2\) $n\ge 2$ vertices that does not contain H or its complement as an induced subgraph has a pure pair of size \(\Omega (n)\) $\mathrm{\Omega }(n)$ ; furthermore, this only holds when H or its complement is a forest. In this paper, we look at pure pairs of size \(n^{1-c}\) $n^{1-c}$ , where \(0<c<1\) $0<c<1$ . Let H be a graph: does every graph on \(n\ge 2\) $n\ge 2$ vertices that does not contain H or its complement as an induced subgraph have a pure pair of size \(\Omega (|G|^{1-c})\) $\mathrm{\Omega }(|G{|}^{1-c})$ ? The answer is related to the congestion of H, the maximum of \(1-(|J|-1)/|E(J)|\) $1-(|J|-1)/|E(J)|$ over all subgraphs J of H with an edge. (Congestion is nonnegative, and equals zero exactly when H is a forest.) Let d be the smaller of the congestions of H and \(\overline{H}\) $\overline{H}$ . We show that the answer to the question above is “yes” if \(d\le c/(9+15c)\) $d\le c/(9+15c)$ , and “no” if \(d>c\) $d>c$ .