  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 Erdos and
Hajnal, which is valid in the class of graphs satisfying any fixed nontrivial
hereditary property. Our result is almost optimal and nearly matches the
celebrated Erdos-Hajnal conjecture, according to which one can always find a
clique or an independent set of size at least $e^{\Omega(\log n)}$. Our results
partially explain why most geometric intersection graphs arising in discrete
and computational geometry have exceptionally favorable Ramsey-type properties.
  Our main tool is a partitioning result found by Lov\'asz-Szegedy and
Alon-Fischer-Newman, which is called the "ultra-strong regularity lemma" for
graphs with bounded VC-dimension. We extend this lemma to $k$-uniform
hypergraphs, and prove that the number of parts in the partition can be taken
to be $(1/\varepsilon)^{O(d)}$, improving the original bound of
$(1/\varepsilon)^{O(d^2)}$ in the graph setting. We show that this bound is
tight up to an absolute constant factor in the exponent. Moreover, we give an
$O(n^k)$-time algorithm for finding a partition meeting the requirements.
Finally, we establish tight bounds on Ramsey-Tur\'an numbers for graphs with
bounded VC-dimension.
