Paperlane

no. 9 · Thursday 5 November 2026

Largest Sperner families with bounded VC-dimension

Gennian Ge, Hanyu Wang, Zixiang Xu and Yixuan Zhang

math.CO · 14 pp

Abstract

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

comments
14 pages
fields
Combinatorics
pdf ↗ page arXiv:2611.06860 ↗