Definition 1.3.1.
Given a set \(X\) and a collection \(\mathcal{F}\subseteq 2^{X}\text{,}\) we say that a set \(S\subseteq X\) is shattered by \(\mathcal{F}\) if
\begin{equation*}
\{F\cap S:F\in\mathcal{F}\} = 2^S\text{.}
\end{equation*}
Section 1.3 VC-Dimension
In other words, a set \(S\) is shattered if every subset of \(S\) can be “represented” as the intersection of \(S\) with a set in \(\mathcal{F}\text{.}\)
Definition 1.3.2.
The VC-dimension of a family \(\mathcal{F}\subseteq 2^{X}\) is the maximum cardinality of a set \(S\subseteq X\) which is shattered by \(\mathcal{F}\text{;}\) if arbitrarily large sets are shattered by \(\mathcal{F}\text{,}\) then the VC-dimension is defined to be \(\infty\text{.}\)
Example 1.3.3.
Suppose that \(\mathcal{F}\) is the collection of all closed intervals \([a,b]\) contained in \(\mathbb{R}\text{.}\) We claim that the VC-dimension of \(\mathcal{F}\) is \(2\text{.}\) Consider \(S=\{1,2\}\text{.}\) We have that
\begin{equation*}
S\cap [3,100] = \emptyset, \qquad S\cap [1.5,5] = \{2\}\text{,}
\end{equation*}
\begin{equation*}
S\cap [0,1.5] = \{1\}, \qquad S\cap [0,3] = \{1,2\}
\end{equation*}
and so \(S\) is shattered by \(\mathcal{F}\text{;}\) this certifies that the VC-dimension is at least two. On the other hand, no set of size 3 or greater can be shattered by \(\mathcal{F}\) since, given three reals \(x\lt y\lt z\text{,}\) there is no interval \([a,b]\) which contains \(x\) and \(z\) but not \(y\text{.}\) Thus, the VC-dimension of \(\mathcal{F}\) is 2.
Example 1.3.4.
Let \(\mathcal{F}\) be the collection of all rectangles of the form \([a,b]\times [c,d]\) in \(\mathbb{R}^2\text{;}\) i.e. axis-aligned rectangles. We claim that the VC-dimension is \(4\text{.}\) Take the set \(S=\{(-1,0),(1,0),(0,1),(0,-1)\}\text{.}\) If you play around for a bit, you can see that, for any subset of \(S\text{,}\) there is an axis-aligned rectangle which intersects \(S\) precisely on that subset; see Figure 1.3.5.
Now, take any set \(S\) of five points in \(\mathbb{R}^2\text{.}\) We can let \(x,y,z\) and \(w\) be the leftmost, rightmost, bottommost and topmost elements of this set, respectively (some of them may be equal). Now, it is not hard to see that there cannot be an axis-aligned rectangle which intersects \(S\) precisely on \(\{x,y,z,w\}\text{.}\) Thus, the VC-dimension is equal to 4.
A natural question is the following: what is the maximum size of a collection \(\mathcal{F}\subseteq 2^{[n]}\) with VC-dimension less than \(k\text{?}\)
Example 1.3.6.
Consider the family \(\mathcal{F}=\bigcup_{i=0}^{k-1}\binom{[n]}{i}\text{.}\) Clearly, \(\mathcal{F}\) cannot shatter any set of cardinality \(k\) as \(\mathcal{F}\) does not even contain a set of this size.
As we will see next, the construction in Example 1.3.6 is optimal.
Theorem 1.3.7. Sauer–Shelah Lemma [252, 262].
If \(\mathcal{F}\subseteq 2^{[n]}\) such that
\begin{equation*}
|\mathcal{F}|> \sum_{i=0}^{k-1}\binom{n}{i}\text{,}
\end{equation*}
then the VC-dimension of \(\mathcal{F}\) is at least \(k\text{.}\)
Proof.
We will actually prove the stronger statement that every non-empty collection \(\mathcal{F}\subseteq 2^{[n]}\) shatters at least \(|\mathcal{F}|\) distinct subsets of \([n]\text{.}\) Given this, the result will follow as there are at most \(\sum_{i=0}^{k-1}\binom{n}{i}\) sets of cardinality less than \(k\text{.}\)
We proceed by induction on \(|\mathcal{F}|\text{.}\) Every non-empty family shatters the empty set, which proves the case \(|\mathcal{F}|=1\text{.}\) Now, suppose that \(|\mathcal{F}|\geq2\) and let \(\mathcal{S}\) be the collection of subsets of \([n]\) shattered by \(\mathcal{F}\text{.}\) Our goal is to prove that \(|\mathcal{S}|\geq|\mathcal{F}|\text{.}\)
Since \(|\mathcal{F}|\geq2\text{,}\) we can choose distinct sets \(F_1,F_2\in\mathcal{F}\text{.}\) After interchanging their names if necessary, we may assume that \(F_1\setminus F_2\neq\emptyset\text{.}\) Choose \(x\in F_1\setminus F_2\) and let
\begin{equation*}
\mathcal{F}_1:= \{F\in\mathcal{F}: x\in F\}
\end{equation*}
and
\begin{equation*}
\mathcal{F}_2:= \{F\in\mathcal{F}: x\notin F\}\text{.}
\end{equation*}
For \(i\in\{1,2\}\text{,}\) let \(\mathcal{S}_i\) be the collection of subsets of \([n]\) shattered by \(\mathcal{F}_i\text{.}\) The families \(\mathcal{F}_1\) and \(\mathcal{F}_2\) partition \(\mathcal{F}\) and, by our choice of \(x\text{,}\) neither of them is empty. So, we can apply the inductive hypothesis to each of them. That is, \(|\mathcal{S}_1|\geq |\mathcal{F}_1|\) and \(|\mathcal{S}_2|\geq |\mathcal{F}_2|\text{.}\)
Now, suppose that \(S\subseteq [n]\) is shattered by either \(\mathcal{F}_1\) or by \(\mathcal{F}_2\text{.}\) Then, by definition of shattering, we immediately get that \(S\) is also shattered by \(\mathcal{F}\text{.}\) Moreover, we observe that \(x\) cannot be an element of \(S\text{;}\) this is because every set in \(\mathcal{F}_1\) contains \(x\) and no set in \(\mathcal{F}_2\) contains \(x\text{.}\) Therefore,
\begin{equation}
\mathcal{S}_1\cup \mathcal{S}_2\subseteq \{S\in \mathcal{S}: x\notin S\}\text{.}\tag{1.3.1}
\end{equation}
Of course, this is not quite enough to finish the proof, since \(\mathcal{S}_1\) and \(\mathcal{S}_2\) may have common elements. However, given any \(S\in \mathcal{S}_1\cap \mathcal{S}_2\text{,}\) recall that \(x\notin S\text{.}\) Since both \(\mathcal{F}_1\) and \(\mathcal{F}_2\) shatter \(S\text{,}\) we get that \(\mathcal{F}\) shatters the set \(S\cup \{x\}\text{.}\) Therefore,
\begin{equation}
\{S\cup\{x\}: S\in \mathcal{S}_1\cap \mathcal{S}_2\}\subseteq \{S\in \mathcal{S}: x\in S\}\text{.}\tag{1.3.2}
\end{equation}
\begin{equation*}
|\mathcal{S}|= |\{S\in \mathcal{S}: x\notin S\}| + |\{S\in \mathcal{S}: x\in S\}|
\end{equation*}
\begin{equation*}
\geq |\mathcal{S}_1\cup\mathcal{S}_2| + |\mathcal{S}_1\cap \mathcal{S}_2|= |\mathcal{S}_1|+|\mathcal{S}_2|
\end{equation*}
\begin{equation*}
\geq |\mathcal{F}_1|+|\mathcal{F}_2|=|\mathcal{F}|
\end{equation*}
and we are done.
Here are a couple of YouTube videos related to VC-Dimension:
