Set Systems with Covering Properties and Low VC-Dimension

George Peterzil, Johanna Steinmeyer

Given natural numbers $k\le s\le n$, we ask: what is the minimal VC-dimension of a family $\mathcal{F}$ of $s$-subsets of $[n]$ that covers all $k$-subsets of $[n]$? We first s…