VC-dimension and Erdős-Hajnal

-
Alex Scott, Oxford University
Fine Hall 224

A class of graphs has the Erdős-Hajnal property if there is some c>0 such that every graph G in the class has a clique or stable set of size at least |G|^c.  Fox, Pach and Suk showed a few years ago that, for every d, the class of graphs with VC-dimension at most d has the "near Erdős-Hajnal property": namely, that there are cliques or stable sets of size exp((log |G|)^{1-o(1)}).  We will show that in fact these classes have the full Erdős-Hajnal property.  Joint work with Tung Nguyen and Paul Seymour.