Erdős-Hajnal for Graphs of Bounded VC-Dimension
Fox, Pach, and Suk recently proved the following lower bound:
The original Erdős-Hajnal Conjecture asserts that the bound should be $e^\alpha\log n$ for some $\alpha >0$.
In terms of upper bounds, the same authors proved:
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:
This seems useful. Maybe it has some applications to Stein’s Tripod-Packing Problem?