$|F| \leq 2{n \choose \lfloor n/2 \rfloor}$ with $F \subset P([n])$

Question

Let $F \subset P([n])$ be a family that doesn't contain three different sets $A, B, C \in F$ with $A \subset B \subset C$.

I have to show that $|F| \leq 2{n \choose \lfloor n/2 \rfloor}$ and that it's optimal for uneven $n$.

---

We could look at $|P([5])|= {5 \choose 0} + {5 \choose 1} +{5 \choose 2} +{5 \choose 3} +{5 \choose 4} +{5 \choose 5} =1 + 5 + 10 + 10+5+1$. ${n \choose k}$ is symmetric, we will have $2$ biggest numbers for uneven $n$ and only $1$ biggest number for even $n$. We have $\binom nk < \binom n{k+1}$ for $n-k > k+1$, it follows immediately that the maximum is in the middle, ${n \choose \lfloor n/2 \rfloor}$. It's clear to me that we will get the biggest family if we take the $2$ biggest sets but how exactly can I show that? It's also clear to me that we shouldn't take the empty set ${n \choose 0}$if we want the biggest family, the empty set is a subset of all sets; and similarly for ${n \choose n}$. But I don't know how to do the rest. And if we stick to our example we could also take like $\{1,2\},\{3,4,5\},\{1,2,3,4\},...$, how do I show that something like this can't be a bigger family?

Answer 1

Here's a hint: define $F_{\mathrm{lower}}=\{A\in F:\text{there exists }B\in F \text{ with }A\subsetneq B\}$ and $F_{\mathrm{upper}}=F\setminus F_{\mathrm{lower}}$. Then show that each of $F_{\mathrm{lower}}$ and $F_{\mathrm{upper}}$ is an antichain and apply Sperner's lemma. Here's a further hint if you still need help:

To show $F_{\text{upper}}$ is an antichain you do not need to use any special properties of $F$. But to show $F_{\text{lower}}$ is an antichain you should use the hypothesis on $F$ that's been given to you.

And finally here's the solution if you're still stuck:

If $F_{\mathrm{upper}}$ is not an antichain, then it contains some pair of elements $A\subsetneq B$. But then $A\in F_{\mathrm{lower}}$ (why?), contradicting that $A\in F_{\mathrm{upper}}$. If $F_{\mathrm{lower}}$ is not an antichain, then it contains some pair of elements $A\subsetneq B$. But by definition of $F_{\mathrm{lower}}$, there then exists $C\in F$ with $B\subsetneq C$. Then $A\subsetneq B\subsetneq C$ are all elements of $F$, contradicting the hypothesis.

Regarding the equality case, you have the right idea! When $n$ is odd, we can take $$F=\{A\subseteq[n]:|A|=\lfloor n/2\rfloor\}\cup\{A\subseteq[n]:|A|=\lceil n/2\rceil\},$$ and this will be of the desired size with the desired properties.

---

As an aside, once you solve this exercise, here's another good extension! Let $k$ be a number, and let $F\subseteq P(n)$ be any family not containing any sequence $A_1\subsetneq A_2\subsetneq\dots\subsetneq A_k$. Then show that $|F|\leqslant (k-1){n\choose\lfloor n/2\rfloor}$. (As a hint, try showing that $F$ can be written as a union of $k-1$ many antichains.)