Dark Mode

21 votes

Best answer

13 votes

**CHAIN :**** **Let (A ,⋨) be a Poset .A subset of A is called Chain if every two elements in the subset are related.

**ANTICHAIN**: A subset of A is called Antichain if no two distinct elements in the subset are related.

**THEOREM: ** Let (A ,⋨) be a Poset.Suppose the length of the longest chains in A is n.Then the elements in A can be partitioned into n disjoint Antichains.

8

@Vicky rix Won't {{1}} and {{2}} also be antichains, in addition to {{1},{2}}.

Edit: Found this source http://mathworld.wolfram.com/Antichain.html

0

6 votes

In a POSET, if an element a is related to some other element b (ie there is an upward path), we call these two elements comparable.

And if not; incomparable.

A chain is nothing but a sequence of distinct comparable elements.

An antichain is a sequence of distinct incomparable elements. Note than a lone element is an antichain despite being comparable to itself.

If the length of the longest chain is n, there are are least n antichains.

Here, the longest chain is: $o\leq a\leq d\leq f\leq g\leq I$. Length is 5.

Antichain partitions are 6.

If the longest chain in a partial order is of length n, then the partial order can be written as a

partitionof n antichains.