zbMATH — the first resource for mathematics

On linear extensions of ordered sets with a symmetry. (English) Zbl 0607.06001
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.
Reviewer: B.Smarda

06A06 Partial orders, general
68P10 Searching and sorting
Full Text: DOI
[1] Fishburn, P.C., On the family of linear extensions of a partial order, J. combin. theory ser. B, 17, 240-243, (1974) · Zbl 0274.06003
[2] Fishburn, P.C., On linear extension majority graphs of partial orders, J. combin. theory ser. B, 21, 65-70, (1976) · Zbl 0294.06001
[3] Graham, R.L., Linear extensions of partial orders and the FKG inequality, () · Zbl 0491.06002
[4] Kahn, J.; Saks, M., Balancing poset extensions, Ordered, 1, 113-126, (1984) · Zbl 0561.06004
[5] N. Linial, The information theoretic bound is good for merging, SIAM J. Comp., to appear. · Zbl 0548.68065
[6] Rival, I., A fixed point theorem for finite partially ordered sets, J. combin. theory ser. A, 21, 309-318, (1976) · Zbl 0357.06003
[7] Saks, M., The information theoretic bound for problems on ordered sets and graphs, () · Zbl 0569.68036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.