A "distinguishing" family of subsets

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.

• But you surely mean $B \subseteq \mathfrak P(A)$, not $B \in \mathfrak P(A)$. May 28 '19 at 16:52

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.

• @YaniorWeg - much as I appreciate the checkmark :) the credit really goes to Fabio, both for coming up with the idea and for a great explanation. As soon as I understood his proof, it's immediately obvious that his row vectors form an antichain / Sperner family, and then it's just a matter of me having heard of Sperner's theorem. May 29 '19 at 12:49

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.