A "distinguishing" family of subsets

Question

Suppose $A$ is a finite set, $B$ is a collection of subsets of $A$, satisfying the following condition:

$$\forall a, b \in A, a \neq b: \exists C \in B: (a \in C) \land (b \notin C)$$

What is the least possible size of $B$.

Currently, I know that the minimal size of $B$ is not less than $\lceil \log_2 |A| \rceil$ (by pigeonhole principle), and it does not exceed $2\lceil \log_2 |A| \rceil$ (an example of that size can trivially be constructed). However, I do not know the exact answer to the question.

Answer 1

The answer by @FabioSomenzi is not just an upperbound - it is actually tight.

• Define $S(a) = \{C \in B: a \in C\}$ for all $a \in A$. Note that $S(a) \subset B$.

• The main condition $\forall a\neq b: \exists C \in B: a \in C \land b \notin C$ becomes $\forall a\neq b: S(a) \not\subset S(b)$

• Therefore the sets $S(a)_{a\in A}$ form a Sperner family of size $|A|$.

• The result now follows from Sperner's theorem, that the maximum sized Sperner family formed by subsets of $B$ has size ${|B| \choose |B|/2}$

---

UPDATE 2019-05-29: Lets see if we can get an estimate on the coefficient. Using Stirling's approximation $n! \sim \sqrt{2 \pi n} ({n \over e})^n$, we have

$${n \choose n/2} = {n! \over (n/2)! (n/2)!} \sim {\sqrt{2 \pi n} ({n \over e})^n \over \sqrt{\pi n} ({n/2 \over e})^{n/2} \sqrt{\pi n} ({n/2 \over e})^{n/2}} = \sqrt{2 \over \pi n} 2^n > |A|$$

So asymptotically we have $n \sim \log_2 |A|$, i.e. the coefficient is $1$, i.e. the pigeonhole-based lower bound is pretty tight.

Answer 2

An improved upper bound is given by the smallest $n$ such that

$$ \binom{n}{\lfloor n/2 \rfloor} \geq |A| \enspace. $$

For $A = \{a,b,c,d,e\}$, we get $n=4$ and, for example, the following encoding: $$ \begin{array}{c|c} a & 1100 \\ b & 1010 \\ c & 1001 \\ d & 0110 \\ e & 0101 \end{array} $$ Reading the columns of the table, $B_1 = \{a,b,c\}, B_2 = \{a,d,e\}, B_3 = \{b,d\}, B_4 = \{c,e\}$. Since each element of $A$ appears in the same number of subsets, and no two elements appear in the same subsets, the condition is satisfied.