Pure Pairs
Location
A "pure pair" in a graph G is a pair (X,Y) of subsets of V(G), disjoint, such that either every vertex in X is adjacent to every vertex in Y, or there are no edges from X to Y. Let f(G) be the biggest k such that G has a pure pair (X,Y) with |X|=|Y|=k. In general f(G) is logarithmic in G, and for any fixed graph H, if G does not contain H as an induced subgraph then f(G) is polynomial in |G|. (This is a result of Erdos, Hajnal and Pach.) But when is f(G) linear in |G|? This question has connections to the Erdos-Hajnal conjecture and to the Gyarfas-Sumner conjecture.
A couple of years ago, we proved a nice thing, a conjecture of Liebenau and Pilipczuk: for any finite set C of graphs, f(G) is linear in |G| for all graphs with no induced subgraph in C, if and only if C contains a forest and the complement of a forest. This result has since grown a number of extensions and variations. (What about bipartite graphs? What about ordered graphs? What about nearly-linear? What if the two sets have different sizes?). We give a tour.
Joint work with Maria Chudnovsky, Jacob Fox, Alex Scott and Sophie Spirkl.