1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.