The Vapnik-Chervonenkis dimension (in short, VC-dimension) of a graph is defined as the VC-dimension of the set system induced by the neighborhoods of its vertices. We show that every $n$-vertex graph with bounded VC-dimension contains a clique or an independent set of size at least $e^{(\log n)^{1 - o(1)}}$. The dependence on the VC-dimension is hidden in the $o(1)$ term. This improves the general lower bound, $e^{c\sqrt{\log n}}$, due to Erdőos and Hajnal, which is valid in the class of graphs satisfying any fixed nontrivial hereditary property. Our result nearly matches the celebrated Erdőos-Hajnal conjecture, according to which one can always find a clique or an independent set of size at least $e^{\Omega(\log n)}$. This partially explains why most geometric intersection graphs arising in discrete and computational geometry have exceptionally favorable Ramsey-type properties.
Joint work with Jacob Fox and Andrew Suk.