The Gateway to Computer Science Excellence

+12 votes

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

+16 votes

Best answer

+15

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

+11

each element of chain must be in different antichains so if chain having n elements so there must exist n disjoint antichains .

+4

https://www.cse.iitb.ac.in/~nutan/courses/cs207-12/notes/lec7.pdf

Reference for more details.

+10

"Subset A of S is called anti chain if no 2 elements in A are comparable".

If i take a total ordered poset(Z,<=) containing n elements then we know every element is comparable to every other. If we take any two of these n, they will also be comparable. So we can take atmost 1 element in a subset A. Total number of such subsets would be n.

Basically in any poset(not only totally ordered) having chain of length n, no two of these n elements can go to the same subset otherwise it won't be an anti chain because "no 2 elements in a subset is comparable". If they belong to same subset then these 2 will be comparable hence won't form an anti chain. So atleast n different subsets for these n elements.

Doubt: Will it be n+1 (1 because of empty subset)? There maybe more such anti chains containing combinations of elements other than these n. But should empty set be considered as an anti chain?

If i take a total ordered poset(Z,<=) containing n elements then we know every element is comparable to every other. If we take any two of these n, they will also be comparable. So we can take atmost 1 element in a subset A. Total number of such subsets would be n.

Basically in any poset(not only totally ordered) having chain of length n, no two of these n elements can go to the same subset otherwise it won't be an anti chain because "no 2 elements in a subset is comparable". If they belong to same subset then these 2 will be comparable hence won't form an anti chain. So atleast n different subsets for these n elements.

Doubt: Will it be n+1 (1 because of empty subset)? There maybe more such anti chains containing combinations of elements other than these n. But should empty set be considered as an anti chain?

+1

Just extra information about What is antichain?

A **chain** in *S* is a subset *C* of *S* in which each pair of elements is comparable; that is, *C* is totally ordered. An **antichain** in *S* is a subset *A* of *S* in which each pair of different elements is incomparable; that is, there is no order relation between any two different elements in *A*.

Reference:https://en.wikipedia.org/wiki/Antichain

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

+7

Ex : number of anti chains in [P(A),subset] where A = {1,2} is 3 (i.e)

1) {} ,

2) {1,2} ,

3) {1} and {2} as {1} and {2} are not related they can form a single anti-chain.

1) {} ,

2) {1,2} ,

3) {1} and {2} as {1} and {2} are not related they can form a single anti-chain.

0

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

52,345 questions

60,470 answers

201,795 comments

95,272 users