Linear Extension Diameter of Downset Lattices of Two-Dimensional Posets
Stefan Felsner, Mareike Massow · SIAM Journal on Discrete Mathematics · 2011
The linear extension diameter of a finite poset $\mathcal{P}$ is the maximum distance between a pair of linear extensions of $\mathcal{P}$, where the distance between two linear extensions is the number of pairs of elements of $\mathcal{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 $\mathcal{D}_{\mathcal{P}}$ of a 2-dimensional poset $\mathcal{P}$, we characterize the diametral pairs of linear extensions of $\mathcal{D}_{\mathcal{P}}$ and show how to compute the linear extension diameter of $\mathcal{D}_{\mathcal{P}}$ in time polynomial in $|\mathcal{P}|$.