VC-saturated set systems

Abstract

The well-known Sauer lemma states that a family $\mathcal{F}\subseteq 2^{[n]}$ of VC-dimension at most $d$ has size at most ${\sum }_{i=0}^d\left(\genfrac{}{}{0ex}{}{n}{i}\right)$. We obtain both random and explicit constructions to prove that the corresponding saturation number, i.e., the size of the smallest maximal family with VC-dimension $d\ge 2$, is at most $4^{d+1}$, and thus is independent of $n$.