The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+8 votes
735 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 in Set Theory & Algebra by Veteran (59.5k points) | 735 views

2 Answers

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

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.

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

answered by Loyal (6.5k points)
+3
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.


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

37,939 questions
45,453 answers
131,194 comments
48,209 users