Building an antichain in a finite poset

175 Views Asked by At

Given some finite poset $P$ we would like to find an antichain $A$ which intersects each maximal chain. How to do that? Note that each chain $C$ and each antichain $A$ intersects at one element as maximum. So, I guess we should do something like that: consider the set of all maximal chains $C_1,C_2,...C_k$. What if we take $x_i\in C_i$ for all $i$ such that $\{x_1,x_2,...x_k\}$ is an antichain? How to do that neatly? I understand the case $k=2$: if every two elements $x_1\in C_1,x_2\in C_2$ can be compared then $C_1\cup C_2$ is also a chain what contradicts maximality of $C_i$. Could you help please?

1

There are 1 best solutions below

0
On

In the case of a finite poset there is a very easy trick.

The set of all maximal elements, or the set of all minimal elements (and by the finiteness assumption both are non-empty). It's not hard to show that every maximal chain must contain a maximal and minimal element (with respect to the entire poset, not just the maximal/minimal in the chain).

So the set of minimal elements must meet every maximal chain. It is also an antichain because two different minimal elements are necessarily incomparable.