Largest Sperner families with bounded VC-dimension

Abstract

A conjecture of Frankl proposed in the 1980s states that for $n\ge 2d$, every Sperner family $\mathcal{F}\subseteq 2^{[n]}$ of VC-dimension at most $d$ has at most $\left(\genfrac{}{}{0ex}{}{n}{d}\right)$ members. We prove this conjecture for every fixed $d$ and large $n$, and show that equality holds only when $\mathcal{F}$ is $\left(\genfrac{}{}{0ex}{}{[n]}{d}\right)$ or $\left(\genfrac{}{}{0ex}{}{[n]}{n-d}\right)$.

arXiv comment14 pages