The ACO Seminar (2018–2019)

The Erdos-Hajnal conjecture states that for every graph $H$, there exists a $c > 0$ such that every $n$-vertex graph $G$ with no induced subgraph isomorphic to $H$ contains a clique or a stable set of size at least $n^c$. A common approach for proving variants of this conjecture is proving that for every graph $H$, every $H$-free $n$-vertex graph $G$ contains two big vertex sets $A$ and $B$ such that either all or none of the edges between them are present in $G$. If $A$ and $B$ always have linear size (in $n$), then the conjecture follows. I will talk about recent progress on this, including some answers for when we can and cannot get one or both of $A$ and $B$ to have linear size. This is joint work with Maria Chudnovsky, Jacob Fox, Alex Scott, and Paul Seymour.

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.