# The Linear-Extension-Diameter of a Poset

###
Stefan Felsner

Institut für Informatik

Freie Universität Berlin

Takustr. 9, D-14195 Berlin, Germany

email: felsner@inf.fu-berli.de

Klaus Reuter

Mathematisches Seminar

Universität Hamburg

Bundesstr. 55, D-20146 Hamburg, Germany

email: reuter@math.uni-hamburg.de

Report B 97-06

June 1997

The * distance * between two permutations of the same set * X * is the number of pairs of elements being in different order in the two
permutations. Given a poset * P=(X,<=) *, a pair * L*_{1},L_{2} of linear extensions is called a * diametral pair * if it maximizes the
distance among all pairs of linear extensions of * P *. The maximal
distance will be called the * linear extension diameter * of * P * and is denoted * led (P) *. Alternatively * led (P) * is the maximum number of incompararable pairs of a two-dimensional extension of * P *. In the first part of the paper we discuss upper and lower bounds for
* led (P) *. These bounds relate * led (P) * to well studied parameters like dimension and height. We prove that * led (P) * is a comparability invariant and determine the linear extension diameter for the class of generalized crowns. For the Boolean lattices we have partial
results.

A diametral pair generates a minimal two-dimensional extension of * P *
or equivalently a maximal interval in the graph of linear extensions
of *P*. Studies of such intervals lead to the definition of new
classes of linear extensions. We give three characterizations of the
class of * extremal linear extensions * which contains the greedy
linear extensions. With * complementary linear extensions * we
introduce a class contained in the set of super-greedy linear
extensions. The complementary linear extension of * L * is the linear
extension * L*^{*} obtained by taking the reverse of * L * as priority list
in the generic algorithm for linear extensions. A * complementary
pair * is a pairs * L,M * of linear extensions with * M=L*^{*<'/sup> } and
* L=M*^{*} . Iterations of the complementary mapping
starting from an arbitrary linear extension eventually leads to
a complementary pair.

Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-97-06.ps.gz