Ganter, Bernhard; Häfner, Gerhart; Poguntke, Werner On linear extensions of ordered sets with a symmetry. (English) Zbl 0607.06001 Discrete Math. 63, 153-156 (1987). 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 Cited in 9 Documents MSC: 06A06 Partial orders, general 68P10 Searching and sorting Keywords:covering graph; finite ordered set; linear extensions; automorphism; sorting PDFBibTeX XMLCite \textit{B. Ganter} et al., Discrete Math. 63, 153--156 (1987; Zbl 0607.06001) Full Text: DOI References: [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, (Rival, I., Ordered Sets (1982), Reidel: Reidel Boston, MA) · 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.; 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, (Rival, I., Graphs and Order (1985), Reidel: Reidel Boston, MA) · 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.