Results 1 to 3 of 3

Math Help - 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; April 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 \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}

    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
    21
    Quote Originally Posted by Defunkt View Post
    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.
    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: December 12th 2010, 02:21 AM
  2. Maximal ideal
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 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: April 19th 2009, 09:20 AM
  5. Maximal ideals of C[x,y]
    Posted in the Advanced Algebra Forum
    Replies: 4
    Last Post: February 10th 2009, 03:49 PM

Search Tags


/mathhelpforum @mathhelpforum