- 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 C of graphs is said to have the Erdős–Hajnal property if every n-vertex graph in C has a clique or stable set of size at least nc. We discuss a proof of a conjecture of Chernikov–Starchenko–Thomas and Fox–Pach–Suk that for every d≥1, the class of graphs of VC-dimension at most d has the Erdős–Hajnal property. Joint work with Alex Scott and Paul Seymour.