1 results
A NOTE ON THE STRONG ERDŐS–HAJNAL PROPERTY FOR GRAPHS WITH BOUNDED VC-MINIMAL COMPLEXITY
- Part of
-
- Journal:
- The Journal of Symbolic Logic , First View
- Published online by Cambridge University Press:
- 15 November 2024, pp. 1-7
-
- Article
-
- You have access
- HTML
- Export citation
-
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 $.
