VC dimension of vector spaces Does the collection of all subspaces of a fixed finite-dimensional vector space have bounded VC dimension?
Could someone please provide references for this question?
 A: I will turn my comment above into a self-contained answer. Given a hypergraph $H=(V,E)$ and $X \subseteq V$, we say that $X$ is shattered if for all $X' \subseteq X$, there exists $e \in E$ such that $e \cap X=X'$.  The VC dimension of $H$ is the size of a largest shattered set.  Given a finite dimensional vector space $\mathbb V$, let $H$ be the hypergraph with vertex set $\mathbb V$ and whose edges are the subspaces of $\mathbb V$.  I claim that the VC dimension of $H$ is $d$, where $d$ is the dimension of $\mathbb V$.  To see this, let $B$ be a basis of $\mathbb V$.  For every subset $A$ of $B$, let $S_A$ be the subspace generated by $A$.  Then $S_A \cap B=A$, and so $B$ is a shattered set of size $d$.  Thus, the VC dimension of $H$ is at least $d$. On the other hand if $X$ is a set of size more than $d$ and $X' \subseteq X$ is a basis for the subspace generated by $X$, then every subspace which contains $X'$ also contains $X$.  Therefore, there is no subspace $S$ such that $S \cap X=X'$, and so $X$ is not a shattered set.
