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

Chains and antichains are there in GATE 2022 syllabus??

### Subscribe to GO Classes for GATE CSE 2022

Suppose the length of the longest chain in a partial order is $n.$ Then the elements in the poset can be partitioned into $n$ disjoint antichains.

could you please explain with an example ?
@Arjun Sir ...not getting this Q/A... antichain  ??

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.

each element of chain must be in different antichains so if chain having n elements so there must exist n disjoint antichains .
Arjun sir not getting this question please explain sir ...
edited
"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?

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

Can someone please give a valid example of Chain and demonstrating creation of Anti chains.

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.

by

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.

@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

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 partition of n antichains.