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?

$\endgroup$
  • $\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 '17 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 '17 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 '17 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 '17 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 '17 at 18:51

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.