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)$

Question

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.

Answer 1

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.