$\newcommand{\N}{\mathbb{N}}\newcommand{\Z}{\mathbb{Z}}\newcommand{\R}{\mathbb{R}}\DeclareMathOperator{\E}{E}$

Fox, Pach, and Suk recently proved the following lower bound:

Every $n$-vertex graph with constant VC-dimension contains a clique or an independent set of size $e^{(\log n)^{1-o(1)}}$.

The original Erdős-Hajnal Conjecture asserts that the bound should be $e^\alpha\log n$ for some $\alpha >0$.

Give a tight bound for the preceding theorem.

In terms of upper bounds, the same authors proved:

For every $s\ge 3$, there exists $n$-vertex graphs of constant VC-dimension that contains no $K_s$ and no independent set of size $c n^{\frac{2}{s+1}}\log n$.

More likely, though, are that I could find applications of these results, since geometric intersection graphs tend to have bounded VC-dimension.

Related to this is the notion of semi-algebraic hypergraphs (graphs whose vertices are points in $\R^d$ and in which a hyper edge $vw$ is present iff the coordinates of $v$ and $w$ satisfy some semi-algebraic condition. Semi-algebraic graphs have bounded VC-dimension, but the actually satisfy stronger conditions:

There exists a constant $\delta >0$ such that every $n$-vertex semi-algebraic graph of bounded complexity contains a complete or an empty bipartite graph whose two parts each have size at least $\delta n$.

This seems useful. Maybe it has some applications to Stein’s Tripod-Packing Problem?