<p>This problem is probably known under some other name, if anyone has seen it before, a reference will be great.</p>

<p>Given $n,m,k$ (for $m,k\ll n$), a $(n,m,k)$ separating set is a set of $n$-sized binary vectors $V$ such that for every disjoint $S,S'\subset \{1,\ldots,n\}$, $|S|=m,|S'|=k$ there exists $v\in V: v_{|S}=0, v_{|S'}=1$.</p>

<p>That is, for every set of $m$ indices $S$ and a non-overlapping set of $k$ indices $S'$, there should be a vector whose $S$ entries are all zeros and his $S'$ entries are all ones.</p>

<p>The goal is to construct a small set $V$ with the above properties.</p>

<blockquote>
  <p>Is this problem known? Are there known deterministic constructions of such $V$? What is the minimal size of such $V$? What about a lower bound?</p>
</blockquote>

<hr>

<p>It seems that it is easy to build $V$ randomly (which would yield $|V|=O(2^{m+k}(m+k)\log n)$ by choosing uniformly distributed i.i.d. vectors).</p>

<p>The $2$ at the base of the exponent can be improved if $m\neq k$ by setting each bit with probability $k/(m+k)$.</p>

<p>Is this an optimal construction?</p>

CC BY-SA 3.0
2017-07-11T00:16:21.283Z
It is too late at night for me to write a real answer, but: If i remember correctly, the optimum is ${m+k \choose k} \cdot O(\log n)$. One can construct sets of size ${m+k \choose k} \cdot 2^{o(m+k)} O(\log n)$. See this paper: http://www.ii.uib.no/~daniello/papers/EfficientRepSet.pdf
Lemma 4.1
daniello
CC BY-SA 3.0
2017-07-11T07:07:29.867Z
Thanks @daniello. I'll be great if you could expand the comment to an answer and/or point me to the relevant part in the paper. There's something that bothers me though. If $m=k$, then it seems that you claim that the optimum is $2^{\Omega(k\log k)}$ while it seems that a random construction gives $2^{O(k)}\log n$. Am I missing something?
R B
CC BY-SA 3.0
2017-07-11T14:05:17.313Z
@R B ${m + k \choose k} \leq 2^{m+k}$ and the base is significantly smaller  than $2$ when $m$ and $k$ are sufficiently different.
daniello
CC BY-SA 3.0
2017-07-11T15:12:40.973Z
Yes, @daniello - you're right. For $m=k$ this gives a base of $2$ and in my application we have $k\approx m$. I didn't follow the analysis all the way, but do you know if this is the number of vectors needed if I set each bit with probability $k/(m+k)$?
R B
CC BY-SA 3.0
2017-07-11T18:51:12.963Z
Yes: $[(k/(m+k))^k \cdot (m/(m+k))^m]^{-1} = {m+k \choose k} \cdot (m+k)^{O(1)}$.
daniello
CC BY-SA 3.0
2017-07-11T18:51:54.270Z
Awesome, thanks!
R B
<ds.algorithms><co.combinatorics><extremal-combinatorics>
How to construct an $(n,m,k)$ ``separating set''?
R B
# How to construct an $(n,m,k)$ ``separating set''?

(Asked by: username_0 on 2017-07-10)

This problem is probably known under some other name, if anyone has seen it before, a reference will be great.

Given $n,m,k$ (for $m,k\ll n$), a $(n,m,k)$ separating set is a set of $n$-sized binary vectors $V$ such that for every disjoint $S,S'\subset \{1,\ldots,n\}$, $|S|=m,|S'|=k$ there exists $v\in V: v\_{|S}=0, v\_{|S'}=1$.

That is, for every set of $m$ indices $S$ and a non-overlapping set of $k$ indices $S'$, there should be a vector whose $S$ entries are all zeros and his $S'$ entries are all ones.

The goal is to construct a small set $V$ with the above properties.

> Is this problem known? Are there known deterministic constructions of such $V$? What is the minimal size of such $V$? What about a lower bound?

---

It seems that it is easy to build $V$ randomly (which would yield $|V|=O(2^{m+k}(m+k)\log n)$ by choosing uniformly distributed i.i.d. vectors).

The $2$ at the base of the exponent can be improved if $m\neq k$ by setting each bit with probability $k/(m+k)$.

Is this an optimal construction?

**Tags:** ds.algorithms, co.combinatorics, extremal-combinatorics
> **Comments:**
> **username_1**: It is too late at night for me to write a real answer, but: If i remember correctly, the optimum is ${m+k \choose k} \cdot O(\log n)$. One can construct sets of size ${m+k \choose k} \cdot 2^{o(m+k)} O(\log n)$. See this paper: http://www.ii.uib.no/~daniello/papers/EfficientRepSet.pdf Lemma 4.1  
> **username_0**: Thanks @daniello. I'll be great if you could expand the comment to an answer and/or point me to the relevant part in the paper. There's something that bothers me though. If $m=k$, then it seems that you claim that the optimum is $2^{\Omega(k\log k)}$ while it seems that a random construction gives $2^{O(k)}\log n$. Am I missing something?  
> **username_1**: @R B ${m + k \choose k} \leq 2^{m+k}$ and the base is significantly smaller  than $2$ when $m$ and $k$ are sufficiently different.  
> **username_0**: Yes, @daniello - you're right. For $m=k$ this gives a base of $2$ and in my application we have $k\approx m$. I didn't follow the analysis all the way, but do you know if this is the number of vectors needed if I set each bit with probability $k/(m+k)$?  
> **username_1**: Yes: $[(k/(m+k))^k \cdot (m/(m+k))^m]^{-1} = {m+k \choose k} \cdot (m+k)^{O(1)}$.  
> **username_0**: Awesome, thanks!  

---

## 0 answers

