Trace of a set family ($T_F(\mathcal{A})$)

For a set family $\mathcal{A}\subseteq \mathcal{P}([n])$ and $F\subseteq [n]$, its trace on $F$ is

A set family $\mathcal{F}$ shatters a set $Z$ when its trace of a set family on $Z$ realizes every subset of $Z$:Each possible include-or-exclude pattern on $Z$ must occur, although different patterns may come from different members of $\mathcal{F}$.

For example, on $X=\{1,2\}$ let $\mathcal{F}=\{\varnothing ,\{1\},\{2\}\}$. It shatters either singleton, but it does not shatter $X$, because the subset $\{1,2\}$ never occurs as a trace of a set family. Its VC dimension is therefore one.

The VC dimension is the largest finite size of a shattered set, or infinity if arbitrarily large finite sets are shattered. The Sauer-Shelah lemma bounds the number of traces when a fixed size cannot be shattered. This turns a local pattern-realization condition into a global bound on the size of a set family.

Partition an infinite countable set into disjoint finite blocks of unbounded size. The union of their power sets consists entirely of finite sets and shatters each block, so it has unbounded finite VC dimension. Every infinite set meets two different blocks. The pair formed by one point from each can never occur as a trace, since each family member stays in one block. Thus no infinite set has traces realizing all its finite subsets.

If every ground element belongs to at least $t$ members of a family $\mathcal{F}\subseteq \mathcal{P}([n])$, thenApply Shearer's inequality to the characteristic vector of a uniformly random member of $\mathcal{A}$.