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.

  • 1
    $\begingroup$ But you surely mean $B \subseteq \mathfrak P(A)$, not $B \in \mathfrak P(A)$. $\endgroup$ 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.

  • $\begingroup$ @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. $\endgroup$
    – antkam
    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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.