1. ## Maximal Antichains

Suppose is a collection of subsets of that is an antichain with regards to inclusion.

Show that

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

Moderator approved: MF

2. Spoiler:

Choose uniformly at random a permutation $\displaystyle \pi \in S_n$. Let $\displaystyle C_\pi = \{\emptyset\} \cup \left\{\pi\left(\{1,...,i\}\right) \ : \ 1 \leq i \leq n\right\}$
And define
$\displaystyle X = |\mathcal{F} \cap C_\pi|$
$\displaystyle 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 $\displaystyle X = \sum_{A \in \mathcal{F}} X_A$. However, from the way we defined $\displaystyle C_\pi$ we also have that for any set A, it contains exactly one set of size $\displaystyle |A|$, distributed uniformly among all sets of size $\displaystyle |A|$. Thus we have that $\displaystyle \mathbb{E}\left[X_A\right] = \frac{1}{\binom{n}{|A|}}$ and so from linearity of expectation, $\displaystyle \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 $\displaystyle C_\pi$ is a chain, we must have that $\displaystyle X=\left|C_\pi \cap \mathcal{F}\right| \leq 1,$ therefore

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

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

3. Originally Posted by Defunkt
Spoiler:

Choose uniformly at random a permutation $\displaystyle \pi \in S_n$. Let $\displaystyle C_\pi = \{\emptyset\} \cup \left\{\pi\left(\{1,...,i\}\right) \ : \ 1 \leq i \leq n\right\}$
And define
$\displaystyle X = |\mathcal{F} \cap C_\pi|$
$\displaystyle 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 $\displaystyle X = \sum_{A \in \mathcal{F}} X_A$. However, from the way we defined $\displaystyle C_\pi$ we also have that for any set A, it contains exactly one set of size $\displaystyle |A|$, distributed uniformly among all sets of size $\displaystyle |A|$. Thus we have that $\displaystyle \mathbb{E}\left[X_A\right] = \frac{1}{\binom{n}{|A|}}$ and so from linearity of expectation, $\displaystyle \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 $\displaystyle C_\pi$ is a chain, we must have that $\displaystyle X=\left|C_\pi \cap \mathcal{F}\right| \leq 1,$ therefore

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

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

I had a novel thought, but never carried through with it. Namely, there's an obvious $\displaystyle S_n$-action on the set of all antichains of $\displaystyle [n]$ by sending $\displaystyle \mathcal{F}=\left\{A_1,\cdots,A_k\right\}$ to $\displaystyle \pi\mathcal{F}=\left\{\pi(A_1),\cdots,\pi(A_k)\rig ht\}$. I was moderately sure then that $\displaystyle \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.