1
$\begingroup$

My question is: is there a standard name for a structure like the following?

For positive integers $n$, $k < n$ define a "$k$-set-free test for $n$" as a set $C$ of subsets of the integers $\{0, \dots, n-1\}$ such that: for every $i \in \{0, \dots, n-1\}$ and every $S \subset \{0, \dots, n-1\} \setminus \{i\}$ with $|S| \le k$ there exists $T \in C$ such that $i \in T$ and $S \cap T = \emptyset$.

Is this a standard combinatorial structure, or a simple transform of a standard combinatorial structure? Does anybody have a convenient reference to this sort of problem?

Follow up notes and questions.

Of interest is: bounding $|C|$.

Our application is: we have an unknown set $B \subset \{0, \cdots, n-1\}$ with $|B| \le k$ of "bad" integers and a test procedure that says a set $T$ is spoiled iff $T \cap B \neq \emptyset$. Find a small set of test-sets to identify $B$ using the test procedure.

Trivially the set $C = \{ \{ i \} | i \in \{0, \dots, n-1\} \}$ is an $n-1$-set-free test for $n$ of size $n$. However, it is easy to show for small $k$ there are $C$ with $|C|$ small (for example $|C| = 2 k \lceil 1 + (k+1) \log_2(n)\rceil $ will do, link).

The problem is a standard error-correcting coding problem if test was working over a field (i.e. counting intersection sizes instead of checking non-emptiness).

Is there an $O(k \log(n))$ sized solution? Or can one establish a lower bound that is larger than that?

| cite | improve this question | | | | |
$\endgroup$
2
$\begingroup$

This is an instance of the set cover problem. I used integer linear programming to obtain the minimum $|C|$ for $1\le k < n \le 12$. Do any of these results surprise you?

\begin{matrix} n\backslash k &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 \\ \hline 2 &2 \\ 3 &3 &3 \\ 4 &4 &4 &4 \\ 5 &4 &5 &5 &5 \\ 6 &4 &6 &6 &6 &6 \\ 7 &5 &7 &7 &7 &7 &7 \\ 8 &5 &8 &8 &8 &8 &8 &8 \\ 9 &5 &9 &9 &9 &9 &9 &9 &9 \\ 10 &5 &9 &10 &10 &10 &10 &10 &10 &10 \\ 11 &6 &9 &11 &11 &11 &11 &11 &11 &11 &11 \\ 12 &6 &9 &12 &12 &12 &12 &12 &12 &12 &12 &12 \\ \end{matrix}

Also, this type of problem is called group testing.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ The references are great and exactly what I needed. The table results are not surprising, as the method isn't going to work until n is much larger than k. Thanks! $\endgroup$ – John Mount Apr 14 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.