A NOTE ON THE STRONG ERDŐS–HAJNAL PROPERTY FOR GRAPHS WITH BOUNDED VC-MINIMAL COMPLEXITY

Abstract Inspired by Adler’s idea on VC minimal theories [1], 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'\subseteq X$ , $Y'\subseteq Y$ with $|X'|\geq k_N |X|$ , $|Y'|\geq k_N |Y|$ such that $X'\times Y' \subseteq E$ or $X'\times Y'\cap E=\emptyset $ .