1
$\begingroup$

Let $N$ be a system of subsets of the set $X = \{1,2,3,\cdots ,n \}$ such that there are no three elements $A,B,C \in N$ such that $A \subset B \subset C$. Prove that $$|N| \leq 2 \cdot {{n}\choose{ \lfloor n/2 \rfloor}}. $$

I have thought about the fact that a semi-independent system of subsets can have at most two elements in common with any chain from $(\mathcal{P}(X), \subseteq),$ but I do not know how to continue using Sperner's theorem.

$\endgroup$
0
$\begingroup$

Let $\mathcal{M}$ be the family of all maximal chains. (We call a chain $\{\varnothing\subsetneq A_1\subsetneq A_2\subsetneq\cdots \subsetneq A_n=X\}\subset 2^X$ of length $n+1$ as a maximal chain.) Define $$ Q=\sum_{M\in \mathcal{M}}\sum_{A\in N} 1_{A\in M} $$ where $1_{A\in M}=1$ if $A\in M$ and is $0$ otherwise. Since for every maximal chain $M\in\mathcal{M}$, there are at most $2$ distinct $A\in N$ such that $A\in M$, we have $$ Q\le\sum_{M\in \mathcal{M}}2=2|\mathcal{M}|=2\cdot n!. $$On the other hand, we have $$ Q=\sum_{A\in N}\sum_{M\in \mathcal{M}}1_{A\in M}=\sum_{A\in N}|A|!(n-|A|)! $$ since the number of maximal chains containing $A$ is $|A|!(n-|A|)!$. Note that $j!(n-j)!$ is minimized when $j=\lfloor \frac{n}{2}\rfloor$. Thus, we have $$ Q= \sum_{A\in N}|A|!(n-|A|)!\ge \lfloor \frac{n}{2}\rfloor!\left(n-\lfloor \frac{n}{2}\rfloor\right)!|N| $$ Gathering them together, we get $$ \lfloor \frac{n}{2}\rfloor!\left(n-\lfloor \frac{n}{2}\rfloor\right)!|N|\le 2\cdot n! $$or $$ |N|\le 2\cdot \frac{n!}{\lfloor \frac{n}{2}\rfloor!\left(n-\lfloor \frac{n}{2}\rfloor\right)!}=2\cdot \binom{n}{\lfloor \frac{n}{2}\rfloor}, $$ as desired.

$\endgroup$
1
$\begingroup$

If $X$ does not contain a $3$-elament chain $A\subset B\subset C$, then $X$ is the union of two antichains. Namely, the set of all minimal elements of $X$ is an antichain, and the set of all non-minimal elements of $X$ is another antichain. By Sperner's theorem, an antichain of subsets of $\{1,2,3,\dots,n\}$ has at most $\binom n{\lfloor n/2\rfloor}$ elements, so your set $X$ has at most twice that many elements.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy