Charles Explorer logo
🇨🇿

Linear extension diameter of level induced subposets of the Boolean lattice

Publikace na Matematicko-fyzikální fakulta |
2014

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

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.