Linear extension diameter of subposets of Boolean lattice induced by two levels |
| |
Authors: | Jiří Fink Petr Gregor |
| |
Affiliation: | Department of Applied Mathematics, Faculty of Mathematics and Physics, Charles University in Prague;Department of Theoretical Computer Science and Mathematical Logic, Faculty of Mathematics and Physics, Charles University in Prague |
| |
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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|