# Maximal Antichains

• Apr 21st 2011, 04:24 AM
Defunkt
Maximal Antichains
Suppose http://quicklatex.com/cache3/ql_0c45...90d6fe9_l3.png is a collection of subsets of http://quicklatex.com/cache3/ql_46ee...64355ff_l3.png that is an antichain with regards to inclusion.

Show that

http://quicklatex.com/cache3/ql_5064...5d198e5_l3.png

There is a very nice probabilistic proof of this. Note also that it is easy to deduce from this that

http://quicklatex.com/cache3/ql_f5b0...c19d361_l3.png

Moderator approved: MF
• May 25th 2011, 12:07 AM
Defunkt
Spoiler:

Choose uniformly at random a permutation $\pi \in S_n$. Let $C_\pi = \{\emptyset\} \cup \left\{\pi\left(\{1,...,i\}\right) \ : \ 1 \leq i \leq n\right\}$
And define
$X = |\mathcal{F} \cap C_\pi|$
$X_A = \left\{\begin{array}{cc} 1 & \ A \in C_\pi \\ 0 & \ \text{otherwise} \end{array}\right. \ \forall A \subset [n]$.

It immediately follows that $X = \sum_{A \in \mathcal{F}} X_A$. However, from the way we defined $C_\pi$ we also have that for any set A, it contains exactly one set of size $|A|$, distributed uniformly among all sets of size $|A|$. Thus we have that $\mathbb{E}\left[X_A\right] = \frac{1}{\binom{n}{|A|}}$ and so from linearity of expectation, $\mathbb{E}[X] = \sum_{A \in \mathcal{F}}\mathbb{E}\left[X_A\right] = \sum_{A \in \mathcal{F}}\frac{1}{\binom{n}{|A|}}$

However, since $C_\pi$ is a chain, we must have that $X=\left|C_\pi \cap \mathcal{F}\right| \leq 1,$ therefore

$1 \geq \mathbb{E}[X] = \sum_{A \in \mathcal{F}}\frac{1}{\binom{n}{|A|}}$

The conclusion follows from the fact that $\binom{n}{x}$ is maximized when $x = \frac{n}{2}$

• May 28th 2011, 11:57 PM
Drexel28
Quote:

Originally Posted by Defunkt
Spoiler:

Choose uniformly at random a permutation $\pi \in S_n$. Let $C_\pi = \{\emptyset\} \cup \left\{\pi\left(\{1,...,i\}\right) \ : \ 1 \leq i \leq n\right\}$
And define
$X = |\mathcal{F} \cap C_\pi|$
$X_A = \left\{\begin{array}{cc} 1 & \ A \in C_\pi \\ 0 & \ \text{otherwise} \end{array}\right. \ \forall A \subset [n]$.

It immediately follows that $X = \sum_{A \in \mathcal{F}} X_A$. However, from the way we defined $C_\pi$ we also have that for any set A, it contains exactly one set of size $|A|$, distributed uniformly among all sets of size $|A|$. Thus we have that $\mathbb{E}\left[X_A\right] = \frac{1}{\binom{n}{|A|}}$ and so from linearity of expectation, $\mathbb{E}[X] = \sum_{A \in \mathcal{F}}\mathbb{E}\left[X_A\right] = \sum_{A \in \mathcal{F}}\frac{1}{\binom{n}{|A|}}$

However, since $C_\pi$ is a chain, we must have that $X=\left|C_\pi \cap \mathcal{F}\right| \leq 1,$ therefore

$1 \geq \mathbb{E}[X] = \sum_{A \in \mathcal{F}}\frac{1}{\binom{n}{|A|}}$

The conclusion follows from the fact that $\binom{n}{x}$ is maximized when $x = \frac{n}{2}$

I had a novel thought, but never carried through with it. Namely, there's an obvious $S_n$-action on the set of all antichains of $[n]$ by sending $\mathcal{F}=\left\{A_1,\cdots,A_k\right\}$ to $\pi\mathcal{F}=\left\{\pi(A_1),\cdots,\pi(A_k)\rig ht\}$. I was moderately sure then that $\displaystyle \sum_{A\in\mathcal{F}}\frac{1}{{n\choose |A|}}\leqslant \left|\text{stab}\left(\mathcal{F}\right)\right|$ from where the conclusion immediately follows. Never worked it out though--maybe I will some other time (assuming it's right).

Nice proof though! I like it.