Induced subgraph density. VI. Bounded VC-dimension

We confirm a conjecture of Fox, Pach, and Suk, that for every d > 0 , there exists c > 0 such that every n -vertex graph of VC-dimension at most d has a clique or stable set of size at least n c . This implies that, in the language of model theory, every graph definable in NIP structures has a clique or anti-clique of polynomial size, settling a conjecture of Chernikov, Starchenko, and Thomas. Our result also implies that every two-colourable tournament satisfies the tournament version of the Erdős-Hajnal conjecture, which completes the verification of the conjecture for six-vertex tournaments. The result extends to uniform hypergraphs of bounded VC-dimension as well. The proof method uses the ultra-strong regularity lemma for graphs of bounded VC-dimension proved by Lovász and Szegedy and the method of iterative sparsification introduced by the authors in an earlier paper.