Shattering coefficient ($s(\mathcal{H},n)$)

The shattering coefficient is

For binary hypothesis classes,because the label vectors realized by the union form the union of the two sets of realized label vectors.

The VC dimension is the largest number of points on which a binary hypothesis class realizes every possible labeling.

If $VC(H)=D<\infty$, then $s(H,n)\le {\sum }_{j=0}^D\left(\genfrac{}{}{0ex}{}{n}{j}\right)$.

The elementary estimate ${\sum }_{j=0}^D\left(\genfrac{}{}{0ex}{}{n}{j}\right)\le (n+1{)}^D$ converts finite VC dimension into a polynomial bound on the number of sample labelings.

The class of lower orthants ${\prod }_{j=1}^p(-\infty ,a_j]$ in ${\mathbb{R}}^p$ has VC dimension at most $p$. Among any $p+1$ points, choose a coordinate maximizer for each of the $p$ coordinates. A remaining point cannot be excluded while all those maximizers are included.

Indicators of real intervals have VC dimension two: two ordered points can be labeled arbitrarily, while an interval containing the two outer points of a triple must contain the middle point.

Intervals together with their label complements shatter three ordered points, but cannot realize an alternating labeling on four, so their VC dimension is three.