YouTube recording: https://www.youtube.com/watch?v=9nzX08hoQEw

Time: Thursday, June 22, 3pm ET
Zoom: https://gatech.zoom.us/j/8802082683

Speaker: Tung Nguyen, Princeton University
Title: More graphs with the Erdős–Hajnal property

Abstract: Erdős and Hajnal conjectured that for every graph $H$, there exists $c>0$ such that every $n$-vertex graph with no induced copy of $H$ contains a clique or stable set of size at least $n^c$. Alon, Pach, and Solymosi reduced this conjecture to the case when $H$ is prime, or equivalently when $H$ is not a blow-up of smaller graphs. Until now, it was not known for any prime $H$ on at least six vertices. This talk describes a construction of infinitely many prime graphs $H$ each satisfying the Erdős–Hajnal conjecture. The proof method actually gives the stronger result that every such $H$ is viral, which will be explained in the talk. Joint work with Alex Scott and Paul Seymour.