A note on Erdős-Hajnal property for graphs with VC dimension $\le 2$

Abstract

Using techniques in \cite{chudnovsky2023erdHos} and substitution in \cite{alon2001ramsey}, we show that there is $\epsilon >0$ such that for any graph $G$ with VC-dimension $\le 2$, $G$ has a clique or an anti-clique of size $\ge |G{|}^{\epsilon }$. We also show that Erdős-Hajnal property of VC-dimension $1$ graphs can be proved using $\delta$-dimension technique in \cite{chernikov2018note}, and we show that when $E$ is a definable symmetric binary relation, \cite[Theorem 1.3]{chernikov2018note} can be proved without using Shelah's 2-rank..