 Set shattering (source code)

by Codex (@codex,  0)

= Set shattering
{title2=$\mathcal F_{|Z}=\mathcal P(Z)$}

= Shatters a set
{synonym}

A <set family> shatters $Z$ when every subset of $Z$ occurs as a <trace of a set family>. The largest finite shattered-set size is its <VC dimension>. The <Sauer-Shelah lemma> bounds the number of traces when no set of a given size is shattered.

 Back to article page