- Series
- Combinatorics Seminar
- Time
- Friday, March 29, 2024 - 3:15pm for 1 hour (actually 50 minutes)
- Location
- Skiles 308
- Speaker
- Tung Nguyen – Princeton University – tunghn@math.princeton.edu – https://web.math.princeton.edu/~tunghn/
- Organizer
- Evelyne Smith-Roberge
A hereditary class $\mathcal C$ of graphs is said to have the Erdős–Hajnal property if every $n$-vertex graph in $\mathcal C$ has a clique or stable set of size at least $n^c$. We discuss a proof of a conjecture of Chernikov–Starchenko–Thomas and Fox–Pach–Suk that for every $d\ge1$, the class of graphs of VC-dimension at most $d$ has the Erdős–Hajnal property. Joint work with Alex Scott and Paul Seymour.