1
$\begingroup$

Here I am considering a set $X$ with $|X| = n$ and it's power set $ \mathcal P(X)$.

Denote by $X^{(i)}$ the set of elements of $\mathcal P(X)$ with $i$ elements, and consider $\mathcal P(X)$ as a poset ordered by $A < B \Leftrightarrow A \subset B$.

Then in my lecture notes, we have Sperner's Theorem saying the largest size of an anti-chain in $\mathcal P(X)$ is $\binom{n}{\lfloor n/2 \rfloor}$, witnessed by $X^{(\lfloor n/2 \rfloor)}$.

Then, to prove this: on realising that for any chain $C$ and anti-chain $A$ of $\mathcal P(X)$ we have that $|C \cap A| \leq 1$, my notes say that: "it is sufficient to partition $\mathcal P(X)$ into $\binom{n}{\lfloor n/2 \rfloor}$ chains".

I understand that on partitioning $\mathcal P(X)$ into this many chains, then we have that an anti-chain can have at most one non-trivial intersection with each of them. Further, we may notice (with appropriately chosen chains) that $X^{\lfloor n/2 \rfloor}$ is indeed a witness to the case of an antichain of size $\binom{n}{\lfloor n/2 \rfloor}$. Together this tells us the maximal anti-chain size is at least $\binom{n}{\lfloor n/2 \rfloor}.$

Why then do we now know there can't be an anti chain that is longer? From what I can tell this proof has given us the wrong bound (lower instead of upper) on the size of the largest possible anti-chain. I expect that I have misunderstood something crucial here, or missed an assumed result, and I would be very grateful if you could point it out to me.

I apologise if I haven't been clear enough here. I have understood what I said here but likely only because I have my lecture notes in front of me. If there is something worth clarifying please let me know.

In case it is important: the method by which we construct the $\binom{n}{\lfloor n/2 \rfloor}$ chains is by using complete matchings from either $X^{(i-1)}$ to $X^{(i)}$ or from $X^{(i)}$ to $X^{(i-1)}$ (order depending on the size of $i$) by viewing $(X^{(i)},X^{(i-1)})$ as a biregular, bipartite graph.

$\endgroup$
3
$\begingroup$

You have chains $C_1,\ldots,C_m$ where $m=\binom{n}{[n/2]}$. Each element of $\mathcal P(X)$ is in exactly one $C_j$. So each element of an antichain $\cal A$ has at most one element in each $C_j$, but each element of $\cal A$ is in some $C_j$, so there are at most $m$ elements in $\cal A$.

I prefer the proof from the LYM inequality....

$\endgroup$
  • 1
    $\begingroup$ it was so simple all along, i feel silly. Thank you for pointing this out to me! $\endgroup$ – user366818 Jul 29 '18 at 18:31
-1
$\begingroup$

On the one hand, you have $\cal{P}$ partitioned into $m= {{n} \choose {\lceil \frac{n}{2}\rceil}}$ chains via the proof in the later part of your post @user, which gives the upper bound of $m$ on the size of the largest antichain.

On the other hand, you have been given an explicit antichain with precisely $m$ elements--namely all subsets of $[n]$ with precisely $\lceil \frac{n}{2} \rceil$ elements, this gives the lower bound of $m$ on the size of the largest antichain.

If both the upper bound and the lower bound on the size of the largest antichain is $m$, then it follows that the size of the largest antichain must indeed be $m$.

$\endgroup$
  • $\begingroup$ Not seeing why this answer was downvoted. A bit late as I saw the comment after, but still correct. $\endgroup$ – Mike Jul 30 '18 at 19:38

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.