Title of article
Linear Extension Diameter of Downset Lattices of 2-Dimensional Posets
Author/Authors
Felsner، نويسنده , , Stefan and Massow، نويسنده , , Mareike، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2009
Pages
5
From page
313
To page
317
Abstract
The linear extension diameter of a finite poset P is the maximum distance between a pair of linear extensions of P , where the distance between two linear extensions is the number of pairs of elements of P appearing in different orders in the two linear extensions. We prove a formula for the linear extension diameter of Boolean Lattices and characterize all pairs of linear extensions attaining the maximum distance. These results can be extended to all downset lattices of 2-dimensional posets.
Keywords
graph diameter , linear extensions , Partial orders , Boolean lattice
Journal title
Electronic Notes in Discrete Mathematics
Serial Year
2009
Journal title
Electronic Notes in Discrete Mathematics
Record number
1455140
Link To Document