Online Talk: Tung Nguyen

YouTube recording:

Time: Thursday, June 22, 3pm ET

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.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.