<p>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$? </p>

<p>Any relevant reference would be of great help.</p>

<p>Thanks!</p>

CC BY-SA 3.0
2012-08-27T12:26:43.687Z
Excuse me for my unfamiliarity, but what is the definition of the VC dimension of a set of 0-1 vectors?
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-27T12:31:38.063Z
@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
CC BY-SA 3.0
2012-08-27T12:34:56.593Z
Then I am afraid that it is incorrect to say "_each_ of VC dimension d."
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-27T12:36:55.950Z
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
CC BY-SA 3.0
2012-08-27T12:39:41.373Z
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
CC BY-SA 3.0
2012-08-27T17:52:56.197Z
Why does $S_{\mathsf{hit}}$ need to be a set of vectors? You can always form a single vector by taking the bitwise and of all vectors in $S_{\mathsf{hit}}$. Do you put restrictions on the weight of vectors in $S_{\mathsf{hit}}$?
Sasho Nikolov
CC BY-SA 3.0
2012-08-29T06:51:56.790Z
@SashoNikolov By intersect i mean S_hit has vectors from every set S_1 upto S_t.
Arun
<co.combinatorics><vc-dimension><epsilon-nets>
Hitting sets for sets of VC dimension d
Arun
# Hitting sets for sets of VC dimension d

(Asked by: username_0 on 2012-08-27)

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!

**Tags:** co.combinatorics, vc-dimension, epsilon-nets

> **Comments:**
> **username_1**: Excuse me for my unfamiliarity, but what is the definition of the VC dimension of a set of 0-1 vectors?  
> **username_0**: @username_1 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.  
> **username_1**: Then I am afraid that it is incorrect to say "_each_ of VC dimension d."  
> **username_1**: 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.  
> **username_0**: 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.  
> **username_2**: Why does $S_{\mathsf{hit}}$ need to be a set of vectors? You can always form a single vector by taking the bitwise and of all vectors in $S_{\mathsf{hit}}$. Do you put restrictions on the weight of vectors in $S_{\mathsf{hit}}$?  
> **username_0**: @SashoNikolov By intersect i mean S_hit has vectors from every set S_1 upto S_t.  

---

## 0 answers

