897 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.
asked | 897 views
+1

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.
answered by Boss (34.1k points)
0
could you please explain with an example ?
0
@Arjun Sir ...not getting this Q/A... antichain  ??
+9

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.

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

​​​​Reference for more details.

0
Arjun sir not getting this question please explain sir ...
+1
"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?

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.

answered by Loyal (7.1k points)
+6
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