×

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

MSC:

06A06 Partial orders, general
68P10 Searching and sorting
PDFBibTeX XMLCite
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.