| Linear Extension Diameter of Downset Lattices of 2-Dimensional Posets (2009) | |||||||||
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 the Boolean Lattice and characterize the diametral pairs of linear extensions. For the more general case of a downset lattice D_P of a 2-dimensional poset P, we characterize the diametral pairs of linear extensions of D_P and show how to compute the linear extension diameter of D_P in time polynomial in |P|.. Comment: 25 pages, 7 figures | |||||||||
Publication details | |||||||||
| |||||||||