# VC-dimension and Ramsey's problem

## János Pach, EPFL, Lausanne and Rényi Institute, Budapest

## March 28, 2017

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.