Interval Orders and Linear Extension Cycles

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,\dots ,x_m$ in the poset such that $p(x_1>x_2)>\frac{1}{2},p(x_2>x_3)>\frac{1}{2},\dots ,p(x_m>x_1)>\frac{1}{2}.$ We settle an open question by showing that interval orders can have LEM cycles.