An upper bound on antichains

Consider the powerset $\mathcal{P}(n)$ (recall that $n$ is equal to the set $\{0, 1, \dots, n - 1\}$). Take some family $\mathcal{F} \subseteq \mathcal{P}(n)$ such that for any distinct $A, B \in \mathcal{F}$, neither $A$ nor $B$ is a subset of the other. What is the maximum number of subsets of $n$ that can be contained in $\mathcal{F}$?

For example, taking $3 = \{0, 1, 2\}$, we may take $\mathcal{F} = \{\{0, 1\}, \{1, 2\}, \{2, 0\}\}$.

I claim the maximum is $\binom{n}{\lfloor \frac{n}{2} \rfloor}$. Equality is obvious, just put every subset of size $\lfloor \frac{n}{2} \rfloor$ into $\mathcal{F}$.

To show the upper bound, we will prove that

$$\sum\limits_{A \in \mathcal F} \frac{1}{\binom{n}{|A|}} \leq 1.$$

This suffices because

$$\sum\limits_{A \in \mathcal F} \frac{1}{\binom{n}{|A|}} \geq \sum\limits{A \in \mathcal F} \frac{1}{\binom{n}{\lfloor \frac{n}{2} \rfloor}} = \frac{|\mathcal F|}{\binom{n}{\lfloor \frac{n}{2} \rfloor}}$$

and multiplying by $|\mathcal F|$ on both sides would yield $|\mathcal F| \leq \binom{n}{\lfloor \frac{n}{2} \rfloor}$. Now we show this bound indeed holds.

Take a random maximal chain $\mathcal{C} \in \mathcal{P}(n)$. For example, taking $3$, we might get $\mathcal{C} = \{\emptyset, \{0\}, \{0, 1\}, \{0, 1, 2\}\}$. And obviously $|\mathcal{F} \cap \mathcal{C}| \leq 1$: remember that no members of $\mathcal F$ are subsets of each other. Thus $E[|\mathcal{F} \cap \mathcal{C}|] \leq 1$.

But by Linearity of Expectation,

$$E[|\mathcal F \cap \mathcal C|] = \sum\limits_{A \in \mathcal F} P[A \in \mathcal C] = \sum\limits_{A \in \mathcal F} \frac{1}{\binom{n}{|A|}}.$$

To elaborate, $P[A \in \mathcal C] = \frac{1}{\binom{n}{|A|}}$ by symmetry: $\mathcal C$ contains exactly one member of cardinality $|A|$, and there are $\binom{n}{|A|}$ such sets in $\mathcal F$ to choose from.

And that’s it!