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 L1,L2 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