Publication at Faculty of Mathematics and Physics |
2014
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 a single adjacent transposition. We determine the linear extension diameter of the subposet of the Boolean lattice induced by the 1st and kth levels and describe an explicit construction of all diametral pairs.
This partially solves a question of Felsner and Massow. The diametral pairs are obtained from minimal vertex-edge covers of so called dependency graphs, a new concept which may be of independent interest.