Paper Info
Title
Linear extension diameter of subposets of Boolean lattice induced by two levels.
Abstract
The linear extension diameter of a finite poset P is the diameter of the graph on all linear extensions of P as vertices, two of them being adjacent whenever they differ in exactly one (adjacent) transposition. Recently, Felsner and Massow determined the linear extension diameter of the Boolean lattice B, and they posed a question of determining the linear extension diameter of a subposet of B induced by two levels. We solve the case of the 1st and kth level. The diametral pairs are obtained from minimal vertex covers of so called dependency graphs, a new concept which may be useful also for the general case.
Year
DOI
Venue
2011
10.1016/j.endm.2011.09.055
Electronic Notes in Discrete Mathematics
Keywords
Field
DocType
Linear extension graph,boolean lattice
Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Linear extension,Boolean algebra (structure),Partially ordered set,Mathematics
Journal
Volume
ISSN
Citations 
38
1571-0653
0
PageRank 
References 
Authors
0.34
5
2
Name
Order
Citations
PageRank
Jiří Fink1829.00
Petr Gregor217819.79