A note on strong Erdős-Hajnal for graphs with bounded VC-minimal complexity

Abstract

Inspired by Adler's idea on VC minimal theories \cite{adler2008theories}, we introduce VC-minimal complexity. We show that for any $N\in {\mathbb{N}}^{>0}$, there is $k_N>0$ such that for any finite bipartite graph $(X,Y;E)$ with VC-minimal complexity $<N$, there exist $X^{\prime }\subseteq X$, $Y^{\prime }\subseteq Y$ with $|X^{\prime }|\ge k_N|X|$, $|Y^{\prime }|\ge k_N|Y|$ such that $X^{\prime }\times Y^{\prime }\subseteq E$ or $X^{\prime }\times Y^{\prime }\cap E=\varnothing$.

New remarks added. Submitted to jsl