Example of tightness of Sauer-Shelah lemma

Question

I was given the task of finding an example of a family of events (or hypothesis, concepts, etc.) such that the Sauer-Shelah lemma is tight.

The lemma states:

Assume that the Vapnik-Chervonenkis dimension (VC-dim) of a family of events $\mathcal{A}$ is $d$. Then for $n \geq d$ $$\mathcal{S}_\mathcal{A}(n) \leq \sum_{i=0}^d{n \choose i}$$ Where $\mathcal{S}_\mathcal{A}$ is the shatter function.

My solution: let $\mathcal{X} = \mathbb{R}$ and $\mathcal{A} = \{x\}_{x \in \mathcal{X}}$. My understanding of VC-dim tells me that $\mathcal{A}$ has VC-dim = 1, since we are not able to shatter more than one point with sets in $\mathcal{A}$.

Now, choose a set with $n$ points $S =\{x_1, ..., x_n\}$. Notice there are $n+1$ different ways to shatter this set using $\mathcal{A}$ (choose each point once and then choose a point $x \not\in S$). Moreover,

$$n+1 = \sum_{i=0}^1{n \choose i} = \underbrace{n \choose 0}_1 + \underbrace{{n \choose 1}}_n$$

Is this example correct ?

Answer 1

Your justification for the VC-dim of $\mathcal{A}$ being $1$ is correct and the example is fine.

As a note, you can generalize your example by considering $\mathcal{A}$ to be the subsets of $\mathbb{R}$ with $d$ elements. This family has VC-dim $d$ and given a subset $S = \{x_1, x_2, ..., x_n\}$, where $n > d$, there are exactly $\sum_{i=0}^d {n\choose i}$ ways in which $d$ points can shatter $S$. Thus,

$$\mathcal{S}_\mathcal{A}(n) = \sum_{i=0}^d {n\choose i}.$$