1
$\begingroup$

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!

Improve this question
$\endgroup$
7
  • $\begingroup$ Excuse me for my unfamiliarity, but what is the definition of the VC dimension of a set of 0-1 vectors? $\endgroup$
    – Tsuyoshi Ito
    Commented Aug 27, 2012 at 12:26
  • 1
    $\begingroup$ @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. $\endgroup$
    – Arun
    Commented Aug 27, 2012 at 12:31
  • $\begingroup$ Then I am afraid that it is incorrect to say "each of VC dimension d." $\endgroup$
    – Tsuyoshi Ito
    Commented Aug 27, 2012 at 12:34
  • $\begingroup$ 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. $\endgroup$
    – Tsuyoshi Ito
    Commented Aug 27, 2012 at 12:36
  • 1
    $\begingroup$ 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. $\endgroup$
    – Arun
    Commented Aug 27, 2012 at 12:39

0

Reset to default

Your Answer

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