0
$\begingroup$

Let X = {1, 2, 3, ... , 100}. Let H be the class of all subsets of X that contain at least 20 and at most 80 elements. What is the VC-dimension of H?

$\endgroup$

1 Answer 1

0
$\begingroup$

The VC dimension is 80.

The set $C=\{1,\dotsc,80\}$ is shattered by $H$:
Let $A\subseteq C$. Note that $|A|\leq|C|=80$. If $|A|\geq20$, then $A\in H$ is already a witness. If $|A|<20$, then $h=A\cup\{81,\dotsc,100\}$ has size between 20 and 39, hence is in $H$, and $h\cap C=A$.

No set of size $\geq81$ is shattered by $H$:
Let $C$ be such a set, and consider $\emptyset\subseteq C$. For any $h\in H$, since $|h|\geq20$, we have $|h\cap C|=|h|+|C|-|h\cup C|\geq 20+81-100>0$, so $h\cap C\neq\emptyset$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.