## Abstract

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≥2 vertices that does not contain H or its complement as an induced subgraph has a pure pair of size Ω(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}, where 0<c<1. Let H be a graph: does every graph on n≥2 vertices that does not contain H or its complement as an induced subgraph have a pure pair of size Ω(|G|^{1-c})? The answer is related to the congestion of H, the maximum of 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 H¯. We show that the answer to the question above is “yes” if d≤c/(9+15c), and “no” if d>c.

Original language | English (US) |
---|---|

Journal | Combinatorica |

DOIs | |

State | Accepted/In press - 2024 |

## All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics
- Computational Mathematics

## Keywords

- Induced subgraphs
- Pure pair
- Sparse