# Subset of $[n]$ without chain of leangth $5$ is of size $\leq \mathcal 2\Biggr(\binom{n}{(n-1)/2}+\binom{n}{(n-3)/2}\Biggl)$

Suppose $$n$$ is odd. Let $$\mathcal P([n])$$ denote the power set of $$[n]$$, that is, the $$2^n$$ subsets of $$\{1,...,n\}$$. We say that a family of sets $$\mathcal F\subseteq \mathcal P([n])$$ is nice if $$\mathcal F$$ does not contain $$5$$ sets $$A,B,C,D,E$$ satisfying $$A\subseteq B \subseteq C \subseteq D \subseteq E$$. Show that if $$\mathcal F \subseteq \mathcal P([n])$$ is nice then:

$$|\mathcal F| \leq 2\Biggr(\binom{n}{(n-1)/2}+\binom{n}{(n-3)/2}\Biggl)$$

I thought looking at $$\mathcal F$$ as a poset with the partial order of set inclusion. It reminds me of Sperner's theorem which I'v learned. I found the following generalization os Sperner's theorem: Let $$\mathcal F$$ be a family of subsets of $$[n]$$ with no chain longer than $$k$$. Then $$\mathcal F \leq$$ Sum of the largest $$k$$ binomial coefficients in $$n$$. This solves the question for $$k=4$$, but I don't know how to prove it.

Any help with solving the original question/the generalization of Sperner's theorem would be appreciated.

The generalized Sperner's theorem is a corollary of the following:

Lemma: For all $$n\ge 0$$, it is possible to partition $$\mathcal P([n])$$ into symmetric chains. A symmetric chain $$C$$ is a list of subsets $$C=( E_1,E_2,\dots,E_k)$$ so that

• $$E_i\subset E_{i+1}$$, for $$i=1,2,\dots,k-1$$.

• $$|E_{i+1}|=|E_i|+1$$, for $$i=1,2,\dots,k-1$$.

• $$|E_1|+|E_k|=n$$.

When $$n=2$$, an example of a symmetric chain partition is $$C_1=(\varnothing,\{2\},\{1,2\}),\qquad C_2=(\{1\})$$ To prove the lemma, we inductively show how to build the chain partition for $$\mathcal P([n])$$ from that of $$\mathcal P([n-1])$$. Let $$\mathcal S_{n-1}=\{C_1,C_2,\dots\}$$ be the chain partition for $$\mathcal P([n-1])$$. Let $$\mathcal T_{n-1}=\{D_1,D_2,\dots\}$$ be the result of adding the element $$n$$ to each entry of each chain in $$\mathcal S_{n-1}$$. Then $$S_{n-1}\cup T_{n-1}$$ is almost a symmetric chain partition of $$\mathcal P([n])$$; the only problem is the chains are not quite symmetric. This is fixed by removing the first subset of each chain in $$S_{n-1}$$, removing any empty chains, and prepending the removed set to the start of the corresponding chain in $$\mathcal T_{n-1}$$. For example, $$\mathcal S_1=\{(\varnothing,\{2\},\{1,2\}),(\{1\})\}\qquad \mathcal T_1=\{(\{3\},\{2,3\},\{1,2,3\}),(\{1,3\})\}\\ \mathcal S_2=\{(\{2\},\{1,2\}),\quad(\varnothing,\{3\},\{2,3\},\{1,2,3\}),(\{1\},\{1,3\})\}$$

$$\square$$

Let's show how this implies the generalized Sperner property. Let $$\mathcal S=\{C_1,C_2,\dots\}$$ be a symmetric chain partition of $$\mathcal P([n])$$. Given a family $$\mathcal F$$ with no chains of length $$r$$, we can replace $$\mathcal F$$ with a new family $$\mathcal F'$$ which has the same number of members of $$\mathcal F$$, but which only occupies the largest $$r-1$$ levels of $$\mathcal P([n])$$. This is done by looking at each chain $$C\in \mathcal S$$, and sliding the members of $$\mathcal F\cap C$$ to the middle $$r$$ entries of $$C$$. Since $$\mathcal F'$$ occupies the middle $$r-1$$ levels, its size is at most the sum of the $$r-1$$ largest binomial coefficients.