Thread: The longest/largest independent set in poset

1. 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!

2. 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 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.

3. 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..

=)

4. Consider these sets.
$\left\{ {2^n :n = 0,1, \cdots ,10} \right\}$
and
$\left\{ {P:P\text{ is prime and }P \le 1996} \right\}$.