Consider the boolean hypercube $\{0,1\}^N$. For a set I $\subseteq$ {1,2,...N}, we define the parity function $h_I$ as follows. For a binary vector x = $(x_1, x_2, ...,x_N) \in \{0,1\}^N$,
$h_I(x) = \bigg(\sum_{i\in I}x_i\bigg)mod 2$
What is the VC-dimension of the class of all such parity functions, $H_{N-parity} = \{h_I:I\subseteq \{1,2,..., N\}\}$? [Courtesy: Shai Ben-David et al.,]
On
$ Claim: VC-dimension(H_{N-Parity})=N $
The upper bound is given by the $\log H_{N-parity}$ , which gives $N $ as there can be at most $2^N$ many such functions.
For the lower bound of the VC-dimension we need to show that there is a set of size $N$ which can be shattered. Let the set be S.
$S=\{x \in {0,1}^N | \sum_{i=1}^N x_i=1\}$
To show $\forall S' \subseteq S, \exists h \in H_{N-Parity} ~such ~that~~ h \cap S=S'$.
Here is $h$ for a particular $S'$.
$$h(x)=\sum_{i=1}^N x_i~, where~ i \in \\{ i \in [N]~ |~ e_i \in S' \\}$$.
In simple engish, h is defined to be parity of the bits which is set to 1 for each element in S'.
We have $\vert H_{N-parity}\vert = 2^N$, and since this is a finite number, we know that VCdim$(H_{N-parity}) \leq \log_2{2^N} = N$. If we can find a subset of $\{0,1\}^N$ of cardinality $N$ which is shattered by $H_{N-parity}$, then we conclude that VCdim$(H_{N-parity})=N$.
But notice that such a set is possible if you take $x_i=e_i$, i.e., the vector of all zeros with a $1$ at the $i_{th}$ position, $i=1, 2, \dots, N$.
Given any subset $K\subset \{1,2,\dots,N\}$, we wish to find a hypothesis $h$ with the property that $h(x_i)=1$ for all $i\in K$. Simply let $I=K$ and the result easily follows.