Combinatorial Proof of $|T| \leq 2 \binom{n}{\lfloor n/2 \rfloor}$

62 Views Asked by At

I need some help proving that if $T$ is a collection of subsets of $\{1,2,3,...,n\}$ such that there doesn't exists $A, B, C \in T$ with $A \subset B \subset C$ then $|T| \leq 2 \binom{n}{\lfloor n/2 \rfloor}$

1

There are 1 best solutions below

2
On BEST ANSWER

Not sure if this proof counts as combinatorial.

Let $T_1=\{B\in T\mid \exists A\in T:B\subsetneq A\}$ and show that $T_1$ and $T\setminus T_1$ are anti-chains, which lets us apply Sperner’s Theorem to both.