THE REVERSAL RATIO OF A POSET

ABSTRACT. Felsner and Reuter introduced the linear extension diameter of a partially ordered set P, denoted led(P), as the maximum distance between two linear extensions of P, where distance is defined to be the number of incompa-rable pairs appearing in opposite orders (reversed) in the linear extensions. In this paper, we introduce the reversal ratio RR(P) of P as the ratio of the linear extension diameter to the number of (unordered) incomparable pairs. We use probabilistic techniques to provide a family of posets Pk on at most k logk el-ements for which the reversal ratio RR(Pk) ≤ C / logk, where C is an absolute constant. We also examine the questions of bounding the reversal ratio in terms of order dimension and width. 1