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

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^{\mathrm{\prime }}\subseteq X$, $Y^{\mathrm{\prime }}\subseteq Y$ with $\mathrm{\mid }{X}^{\mathrm{\prime }}\mathrm{\mid }\ge k_N\mathrm{\mid }X\mathrm{\mid }$, $\mathrm{\mid }{Y}^{\mathrm{\prime }}\mathrm{\mid }\ge k_N\mathrm{\mid }Y\mathrm{\mid }$ such that $X^{\mathrm{\prime }}\times Y^{\mathrm{\prime }}\subseteq E$ or $X^{\mathrm{\prime }}\times Y^{\mathrm{\prime }}\cap E=\mathrm{\varnothing }$.