Generating Linear Extensions of Posets by Transpositions

Frank Ruskey, Department of Computer Science, University of Victoria, Canada.

Abstract:

This paper considers the problem of listing all linear extensions of a partial order so that successive extensions differ by the transposition of a single pair of elements. A necessary condition is given for the case when the partial order is a forest. A necessary and sufficient condition is given for the case where the partial order consists of disjoint chains. Some open problems are mentioned.

Notes

The postscript file 291943 bytes, the dvi file is 109,152 bytes.
Appears in J. Combinatorial Theory (B), 54 (1992) 77-101.
An editorial decision was made to omit certain parts of the original manuscript (this decision not suggested by the referees however). The original longer paper is available here in postscipt (348,782 bytes) or in dvi (150,628 bytes) format.
A preliminary announcement of some of these results appeared in: F. Ruskey, A Hamilton Path in the Transposition Graph for Multiset Permutations, 19th S.E. Conference on Combinatorics, Graph Theory, and Computing, Congressus Numeratium, 67 (1988) 27-34.
Extensions of some of these results (particularly for adjacent transpositions) may be found in: G. Stachowiak, Hamilton Paths in Graphs of Linear Extensions for Unions of Posets, SIAM J. Discrete Mathematics, 5 (1992) 199-206.

Selected papers that reference this paper

G. Stachowiak, Hamilton Paths in Graphs of Linear Extensions for Unions of Posets, SIAM J. Discrete Mathematics, 5 (1992) 199-206.
White, Dennis E. Sign-balanced posets. J. Combin. Theory Ser. A 95 (2001), no. 1, 1-38. [MR1840476 (2002e:05151), 05E10 (05A15 05E05 06A07)]
Richard Stanley, Some remarks on sign-balanced and maj-balanced posets, Advances in Applied Math., to appear.
Jayme L. Szwarcfiter, Generating All Forest Extensions of a Partially Ordered Set, Lecture Notes in Computer Science, Volume 2653, Algorithms and Complexity: 5th Italian Conference, CIAC 2003, Rome, Italy, May 28-30, 2003, pp. 132 - 139.
Ron M. Adin and Yuval Roichman, Equidistribution and Sign-Balance on 321-Avoiding Permutations (14 pp.), Séminaire Lotharingien de Combinatoire, Issue 51, 2003.
Il'yuta, G. G., A'Campo-Gusein-Zade diagrams as partially ordered sets, (Russian) Izv. Ross. Akad. Nauk Ser. Mat. 65 (2001), no. 4, 49-66; translation in Izv. Math. 65 (2001), no. 4, 687-704. [MR1857710 (2002i:58052), 58K20 (06A06 16G20 58K40)]
Kostov, V. P. and Shapiro, B., On arrangements of roots for a real hyperbolic polynomial and its derivatives, Bulletin des Sciences Mathématiques, Elsevier, 126 (2002), no. 1, 45--60
Kostov, V. P., Root configurations for hyperbolic polynomials of degree 3, 4, and 5. (Russian) Funktsional. Anal. i Prilozhen. 36 (2002), no. 4, 71-74; translation in Funct. Anal. Appl. 36 (2002), no. 4, 311-314 12D10. [MR1958997]
Jonas Sjöstrand, On the sign-imbalance of skew partition shapes, European Journal of Combinatorics, 28 (2007) 1582-1594.
Thomas Lam, Signed differential posets and sign-imbalance, Journal of Combinatorial Theory, Series A, 115 (2008) 466-484.
Karell De Loof, Dernard De Baets, Hans De Meyer, Rainer Bruggemann, A Hitchhiker's Guide to Poset Ranking, Combinatorial Chemistry and High Throughput Screening, 11 (2008) 734-744.

Back to list of publications.