Growth function of a binary hypothesis class

Let $(\mathcal{X},\mathrm{\Sigma })$ be a nonempty measurable space and let $H$ be a nonempty class of measurable binary functions on $\mathcal{X}$. For each integer $m\ge 0$, the growth function of $H$ is

${\mathrm{\Pi }}_H(m):={\sup }_{\mathbf{x}\in {\mathcal{X}}^m}\mathrm{\mid }{\mathrm{tr}}_H(\mathbf{x})\mathrm{\mid }\mathrm{.}$

The supremum is a maximum because each trace size is an integer between $1$ and $2^m$ and ${\mathcal{X}}^m$ is nonempty. In particular, ${\mathrm{\Pi }}_H(0)=1$. A finite indexed tuple is shattered exactly when its trace has size $2^m$, so $\mathrm{VCdim}(H)=\sup \{m\in {\mathbb{N}}_0:{\mathrm{\Pi }}_H(m)=2^m\}$.

Indexed shattering and VC dimension of a binary class: ${\mathrm{tr}}_H(\mathbf{x})$ is the set of binary label vectors on the indexed tuple $\mathbf{x}$, and shattering means that this trace is all of $\{0,1{\}}^m$.

Mohri et al., Definition 3.6 and equation (3.19): the growth function counts distinct dichotomies on a sample.

Bartlett and Mendelson, Theorem 6: restriction of a class to a fixed sample and its empirical VC dimension.