in Set Theory & Algebra retagged by
4,375 views
16 votes
16 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.
in Set Theory & Algebra retagged by
4.4k views

4 Comments

12
12
Chains and antichains are there in GATE 2022 syllabus??
0
0

Can we also say that partial order relation can be written as union of n anti chains ?

0
0
not  always
0
0

3 Answers

21 votes
21 votes
Best answer
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.

4 Comments

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

@MiNiPanda We won’t consider empty subset, partitions of set are disjoint and non-empty

1
1
13 votes
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.

2 Comments

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.
8
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
0
6 votes
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.

Source: https://www.researchgate.net/figure/Two-possible-antichain-partitions-on-the-Hasse-diagram_fig3_313376303

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.

1 comment

Here 9 antichain partitions also possible right?

when all single elements are considered.
0
0

Related questions