Half-power-set trace growth forces finite shattering
= Half-power-set trace growth forces finite shattering
{title2=$|\mathcal F_{|Y}|\geq2^{2k-1},\ |Y|=2k\Longrightarrow\exists Z\subseteq Y,\ |Z|=k$}
If no $k$-set were shattered, the <Sauer-Shelah lemma> would bound the number of traces by $\sum_{i<k}\binom{2k}{i}=(2^{2k}-\binom{2k}{k})/2<2^{2k-1}$. This strict middle-layer gap contradicts the displayed lower bound. Therefore a family with such traces at every even size has unbounded finite <VC dimension>.