retagged by
5,675 views
19 votes
19 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.
retagged by

3 Answers

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

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.

Related questions

51 votes
51 votes
4 answers
1
Kathleen asked Sep 12, 2014
11,427 views
The maximum number of possible edges in an undirected graph with $n$ vertices and $k$ components is ______.
16 votes
16 votes
1 answer
2
Kathleen asked Sep 12, 2014
3,136 views
A given set of processes can be implemented by using only parbegin/parend statement, if the precedence graph of these processes is ______
37 votes
37 votes
1 answer
3
Kathleen asked Sep 12, 2014
4,777 views
When two $4$-bit numbers $A = a_3a_2a_1a_0$ and $B=b_3b_2b_1b_0$ are multiplied, the bit $c_1$ of the product $C$ is given by ________
24 votes
24 votes
3 answers
4
Kathleen asked Sep 12, 2014
4,367 views
Consider the following PASCAL program segment:if i mod 2 = 0 then while i >= 0 do begin i := i div 2; if i mod 2 < 0 then i := i - 1; else i := i – 2; end;An appropria...