Pure Pairs

Abstract:

A “pure pair” in a graph $G$ is a pair $(X,Y)$ of disjoint subsets of $V(G)$ 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|$ at least $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|$?

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 $C$ contains a forest and the complement of a forest. This result has grown a number of extensions and variations since. (What about bipartite graphs? What about ordered graphs? What about nearly-linear? What if the two sets have different sizes?).

Joint work with Maria Chudnovsky, Alex Scott and Sophie Spirkl.

This talk is hosted by Stanford University. Link to the talk site.