Shattering-extremal set systems of VC dimension at most 2

Tamás Mészáros, Lajos Rónyai

We say that a set system $\mathcal{F}\subseteq 2^{[n]}$ shatters a given set $S\subseteq [n]$ if $2^S=\{F\cap S:F\in \mathcal{F}\}$. The Sauer inequality states that in general…