Linear Extension Diameter of Downset Lattices of 2-Dimensional Posets

2009/07/10 by Stefan Felsner, Felsner, Stefan, Mareike Massow +1
Mathematics · #06A07 #06B05 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:06A07 #msc:06B05

paper · pdf · doi:10.48550/arxiv.0907.1793

25 pages, 7 figures

arxiv created 2009/07/10 · arxiv updated 2009/12/01

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|.

Related

• Diametral Pairs of Linear Extensions
• On the Minimum Width of a Cutset in the Truncated Boolean Lattice
• On Lattice Diameter Segments and A Discrete Borsuk Partition Problem
• On lattice extensions
• Small Shadows of Lattice Polytopes