Prove that each chain in a symmetric chain partition contains exactly one $\lfloor n/2 \rfloor$ subset

716 Views Asked by At

enter image description here

Here, the order is set inclusion. My textbook (Brunaldi) is considering $\{n\}$-sets.

Let $X = \{1, 2, \dots n\}$.

I can see why each of $$\binom{n}{\lfloor n/2 \rfloor}$$ $\lfloor n/2 \rfloor$-subsets of P($\{n\}$) must belong to different chains. This is true, since the longest anti-chain of $\{n\}$ is the antichain of $\lfloor n/2 \rfloor$-subsets, and a chain cannot contain more than one member of an antichain.

This convinces me that we must have at least $$\binom{n}{\lfloor n/2 \rfloor}$$ symmetric chains, not exactly that many.

Why must there be exactly that many?

1

There are 1 best solutions below

0
On

Hint:

Prove this fact then you are done:

Let $S$ be a set of $n$ elements. Prove that, if $n$ is even, the only antichain of size $\binom{n}{\lfloor n/2 \rfloor}$ is the antichain of all $n/2$ subsets; if $n$ is odd, prove that the only antichains of this size are the antichain of all $n-1/2$ subsets and the antichain of all $n+1/2$ subsets.