Erdős–Hajnal and VC-dimension (Tung Nguyen, Princeton)

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.eduhttps://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 d1, the class of graphs of VC-dimension at most d has the Erdős–Hajnal property. Joint work with Alex Scott and Paul Seymour.