# What is a reference for this sort of test set system that avoids all sets of size $\le k$?

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?

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?

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}$$