The longest/largest independent set in poset

• Jan 2nd 2010, 02:57 AM
Dandelion
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 (Worried) and I would be really grateful if someone could explain me on this example the method of solving similar problems... Thanks in forward!
• Jan 2nd 2010, 06:30 AM
Plato
Quote:

Originally Posted by Dandelion
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 (Worried) 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.
• Jan 2nd 2010, 07:59 AM
Dandelion
Quote:

Originally Posted by Plato
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..

=)
• Jan 2nd 2010, 08:53 AM
Plato
Consider these sets.
$\displaystyle \left\{ {2^n :n = 0,1, \cdots ,10} \right\}$
and
$\displaystyle \left\{ {P:P\text{ is prime and }P \le 1996} \right\}$.