4
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ 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: ii.uib.no/~daniello/papers/EfficientRepSet.pdf Lemma 4.1 $\endgroup$
    – daniello
    Jul 11, 2017 at 0:16
  • $\begingroup$ 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? $\endgroup$
    – R B
    Jul 11, 2017 at 7:07
  • $\begingroup$ @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. $\endgroup$
    – daniello
    Jul 11, 2017 at 14:05
  • $\begingroup$ 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)$? $\endgroup$
    – R B
    Jul 11, 2017 at 15:12
  • 1
    $\begingroup$ Yes: $[(k/(m+k))^k \cdot (m/(m+k))^m]^{-1} = {m+k \choose k} \cdot (m+k)^{O(1)}$. $\endgroup$
    – daniello
    Jul 11, 2017 at 18:51

0

Reset to default

Your Answer

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