On linear extensions of ordered sets with a symmetry (Q1085187)

A linear extension of a finite ordered set \((P,<)\) is an order-preserving bijection \(\lambda\) : \(P\to \{1,2,...,| P| \}\). For any pair x, y of distinct elements in P, \(p(x<y)\) denotes the fraction of linear extensions such that \(\lambda (x)<\lambda (y)\). The authors prove the following theorem: Let \((P,<)\) be a finite cycle-free ordered set, and let \(\alpha\) be a non-trivial automorphism of \((P,<)\). Then \(p(x<\alpha (x))=1/2\) for any \(x\in P\) with \(\alpha\) (x)\(\neq x\). The motivation for this comes from sorting problems.