Interval Orders and Linear Extension Cycles

Graham Brightwell1, Peter C.Fishburn2, Peter Winkler3
1London School of Economics and Political Science Houghton St., London WC2A 2AE United Kingdom
2AT & T Bell Laboratories Murray Hill, New Jersey 07974 US.A,
3Bell Communications Research Morristown, New Jersey 07960 US.A.

Abstract

Let \(p(x > y)\) be the probability that a random linear extension of a finite poset has \(x\) above \(y\). Such a poset has a LEM (linear extension majority) cycle if there are distinct points \(x_1, x_2, \ldots, x_m\) in the poset such that \(p(x_1 > x_2) > \frac{1}{2}, p(x_2 > x_3) > \frac{1}{2}, \ldots, p(x_m > x_1) > \frac{1}{2}.\) We settle an open question by showing that interval orders can have LEM cycles.