Results 1 to 3 of 3

Thread: Maximal Antichains

  1. #1
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976

    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
    Last edited by mr fantastic; Apr 21st 2011 at 01:25 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    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}$

    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    22
    Quote Originally Posted by Defunkt View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. a maximal ideal
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Dec 12th 2010, 02:21 AM
  2. Maximal ideal
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Nov 10th 2010, 06:47 AM
  3. is ideal maximal?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 27th 2009, 01:16 PM
  4. Maximal Ideal
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Apr 19th 2009, 09:20 AM
  5. Maximal ideals of C[x,y]
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: Feb 10th 2009, 03:49 PM

Search Tags


/mathhelpforum @mathhelpforum