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) 77101.

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) 2734.

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) 199206.
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) 199206.

White, Dennis E. Signbalanced posets.
J. Combin. Theory Ser. A 95 (2001), no. 1, 138.
[MR1840476 (2002e:05151),
05E10 (05A15 05E05 06A07)]

Richard Stanley,
Some remarks on signbalanced and majbalanced 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 2830, 2003,
pp. 132  139.

Ron M. Adin and Yuval Roichman,
Equidistribution and SignBalance on 321Avoiding Permutations (14 pp.),
Séminaire Lotharingien de Combinatoire, Issue 51, 2003.

Il'yuta, G. G.,
A'CampoGuseinZade diagrams as partially
ordered sets, (Russian) Izv. Ross. Akad. Nauk Ser. Mat. 65
(2001), no. 4, 4966; translation in Izv. Math. 65 (2001),
no. 4, 687704.
[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, 4560

Kostov, V. P., Root configurations for hyperbolic polynomials of
degree 3, 4, and 5. (Russian) Funktsional. Anal. i Prilozhen.
36 (2002), no. 4, 7174; translation in Funct. Anal. Appl.
36 (2002), no. 4, 311314 12D10.
[MR1958997]

Jonas Sjöstrand,
On the signimbalance of skew partition shapes,
European Journal of Combinatorics, 28 (2007) 15821594.

Thomas Lam,
Signed differential posets and signimbalance,
Journal of Combinatorial Theory, Series A,
115 (2008) 466484.

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) 734744.
Back to list of publications.