# Hitting sets for sets of VC dimension d

Let $S$ be a collection of sets of binary vectors (in $\{0,1\}^m$) $S_1, S_2, \dotsc, S_t$ (say $t = O(m^d)$) each of VC dimension $d$. What can be said about the size of a hitting set $S_\text{hit}$ which consists of binary vectors that intersect every set $S_1, \dotsc, S_t$?

Any relevant reference would be of great help.

Thanks!

• Excuse me for my unfamiliarity, but what is the definition of the VC dimension of a set of 0-1 vectors? – Tsuyoshi Ito Aug 27 '12 at 12:26
• @Tsuyoshi Ito Each binary vector can be seen as the indicator vector of a set on the domain [m]. The VC dimension is just the VC dimension of the set system formed by the set of vectors. – Arun Aug 27 '12 at 12:31
• Then I am afraid that it is incorrect to say "each of VC dimension d." – Tsuyoshi Ito Aug 27 '12 at 12:34
• Oh, I now see, each S_i is a set of vectors, so each S_i is a set system. Sorry, you are right, my two previous comments were bogus. – Tsuyoshi Ito Aug 27 '12 at 12:36
• In the case i am interested in, each of the sets S1, S2 etc is of VC dimension d. For instance for m=2,d=1 one could have S1 = {[0 0],[0 1]} and S2 = {[1 0],[1 1],[0 1]}. Both S1 and S2 are of VC dimension 1. The union of S1,S2 might have a larger VC dimension.(which is 2 in the example). (The hitting set i am interested in is S_hit = {[0 1]}). Hope i am clear now. – Arun Aug 27 '12 at 12:39