Erdős–Hajnal and VC-dimension (Tung Nguyen, Princeton)
- Series
- Combinatorics Seminar
- Time
- Friday, March 29, 2024 - 15:15 for 1 hour (actually 50 minutes)
- Location
- Skiles 308
- Speaker
- Tung Nguyen – Princeton University – tunghn@math.princeton.edu
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.