Separating set system

Question

Let $[n]$ denote the integers from 1 to n. I'm interested in a family of subsets $\{C_k\}$ such that for all $i \neq j$ there exists a set $C_k$ such that either $i \in C_k$ and $j \notin C_k$ or $j \in C_k$ and $i \notin C_k$. Does anyone know what such a subset system is called? Also, what are the known bounds on the size of this family?

Answer 1

If we let $A_i$ denote the set of $t$ for which $S_t$ contains $i$, your statement is equivalent to the statement that no two $A_i$ are identical. This gives the bound that $2^{|F|} \geq n$, meaning your family must have size at least $\lceil \log_2 n \rceil$ This bound is achievable, for example, by letting $S_i$ be the numbers with a $1$ in the $i^{th}$ bit when written in binary.

In the computer science literature, this property is referred to as the weak $2-$selector property. More generally, a weak $k$ selector is a family of sets for which, given any subset of $k$ sets, we can find an element contained in exactly one set from the subset. A strong selector would be similar, except now we want there to be an element unique to each of the $k$ sets in each subset of size $k$. For $k=2$ (the analogue of your problem) a strong selector would be saying that for every $i \neq j$ we can find a set containing $i$ but not $j$ and a set containing $j$ but not $i$.

For $k=2$ strong selectors are dual to antichains, and Sperner’s Theorem gives the optimal size.