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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.