in Set Theory & Algebra retagged by
3,016 views
13 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
3k views

2 Comments

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

Subscribe to GO Classes for GATE CSE 2022

3 Answers

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

10 Comments

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

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.

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

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

1
Can someone please give a valid example of Chain and demonstrating creation of Anti chains.
0
1
12 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.
7

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

Related questions

Ask
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true