×

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
PDF BibTeX XML Cite