zbMATH — the first resource for mathematics

Interval orders and linear extension cycles. (English) Zbl 0798.06002
Summary: 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)> 1/2$$, $$p(x_ 2> x_ 3)> 1/2,\dots, p(x_ m> x_ 1)> 1/2$$. We settle an open question by showing that interval orders can have LEM cycles.

MSC:
 06A06 Partial orders, general