If I have the input space of (1,2,....999). And I have a concept class C, with 10 concepts: C0,C1,C2...C9.
Given an input, that input is an element of ci if the it contains the digit i. For example, the number 123 is an element of c1 and c2 and c3.
What is the VC Dimension of this concept class C?
I don't want to post the whole solution here, but here's something...
Finding the VC dimension involves finding sets of points in the input space that can be shattered by C.
I can easily find a set of three points that can be shattered by C, (14, 24, 3).
It's harder to find a set of four points that can be shattered by C, but (157, 256, 367, 4) works.
It's very, very hard to find five points that can be shattered by C, which strongly suggests that the VC dimension of C (given the input space) is 4. However, the tricky part is proving that it's impossible to find any set of five points that can be shattered.
Actually, there may be some ambiguity in the question. It depends in what sense the concept class can 'correctly classify' a set of points. i.e. Does C1 correctly classify (1, 2) where 1 is given a negative class label and 2 is given a positive one (since it partitions it correctly), or can only C2 do that? I've assumed that it can, because the problem is slightly more interesting that way.