ÍâÍøÌìÌÃ

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.