Results 1 to 4 of 4

Math Help - The longest/largest independent set in poset

  1. #1
    Newbie
    Joined
    Dec 2009
    Posts
    9

    The longest/largest independent set in poset

    Hello once again =)

    There is a partially ordered set (S,X) where S={(x,y); x|y} and X={1,2,...,1996}. The task is to find the longest independent set in this poset, and the opposite - the longest ''string'' in the poset. I am not sure if I used correct terms in English, so I really hope someone will understand what was in my mind =)

    Anyway, I have a lot of tasks of this type and I would be really grateful if someone could explain me on this example the method of solving similar problems... Thanks in forward!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,663
    Thanks
    1616
    Awards
    1
    Quote Originally Posted by Dandelion View Post
    Hello once again =)

    There is a partially ordered set (S,X) where S={(x,y); x|y} and X={1,2,...,1996}. The task is to find the longest independent set in this poset, and the opposite - the longest ''string'' in the poset. I am not sure if I used correct terms in English, so I really hope someone will understand what was in my mind =)

    Anyway, I have a lot of tasks of this type and I would be really grateful if someone could explain me on this example the method of solving similar problems... Thanks in forward!
    I think that you must give us some examples of independent sets and strings.
    Both these words have multiple meanings.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Dec 2009
    Posts
    9
    Quote Originally Posted by Plato View Post
    Both these words have multiple meanings.
    I apologize, in the meantime I managed to find correct terms. Actually the task is to find maximal chain and antichain. I hope that makes sense now..

    =)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,663
    Thanks
    1616
    Awards
    1
    Consider these sets.
    \left\{ {2^n :n = 0,1, \cdots ,10} \right\}
    and
    \left\{ {P:P\text{ is prime and }P \le 1996} \right\}.
    Last edited by Plato; January 2nd 2010 at 09:49 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Longest run in 50 tosses
    Posted in the Statistics Forum
    Replies: 9
    Last Post: July 3rd 2011, 10:37 PM
  2. Longest possible chess game
    Posted in the Advanced Math Topics Forum
    Replies: 7
    Last Post: October 9th 2010, 06:56 PM
  3. Poset troubles
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 5th 2010, 08:56 AM
  4. give a poset that has ...
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 27th 2008, 05:40 PM
  5. poset
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 9th 2006, 08:27 AM

Search Tags


/mathhelpforum @mathhelpforum