Thread: 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!

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.

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

=)

Consider these sets.

and
.