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?
