ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

14. Mathematical Aspects of Computer Science

1991 MS Classification: 06A07, 05C12 Felsner, Stefan, Freie Univ. Berlin, Germany The Linear-Extension-Diameter 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. 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. We also study heuristic ideas for approximating led(P). This leads to some new interesting classes of linear extensions.