This page provides some additional material for my workshop
Combinatorial Choreography
at Bridges 2012,
and our paper Lehmer's Dance -- a lecture performance at Bridges 2019.
D.H. Lehmer,
"Permutation by Adjacent Interchanges",
The American Mathematical Monthly, Vol. 72, No. 2,
Part 2: Computers and computing (Feb. 1965), pp. 36-46.
P. Eades, M. Hickey and R. Read.
"Some Hamilton Paths and a Minimal Change Algorithm",
Journal of the ACM, Vol.31, pp.19--29 (1984).
This article proves the theorem that
the neighbor-swap graph on n-bit strings (combinations)
admits a Hamilton path if and only if
it is trivial or the number of 0s and 1s are both odd.
F. Ruskey.
"Solution to Some Lattice Paht Parity Differnce Recurrence Relations
using Involutions",
Congressus Numerantium, 59:257-264 (1987).
This article actually already presents a proof
(for the necessity of two odd counts in the binary case)
based on (what I call) stutter permutations.
C.W. Ko, F. Ruskey.
"Solution of Some Multi-dimensional Lattice Path
Parity Difference Recurrence Relations",
Discrete Mathematics, 71:47-56 (1988).
This article proves a necessary condition for the existence of
a Hamilton path on the neighbor-swap graph on the permutations
of a non-trivial multiset, viz. that at least two elements in the multiset
occur an odd number of times.
G. Stachowiak.
"Hamilton Paths in Graphs of Linear Extensions for Unions of Posets",
SIAM Journal on Discrete Mathematics, Vol.5, Nr.2, pp.199-206 (1992).
This article (constructively) proves the sufficiency part of
the conjecture that
the neighbor-swap graph on the permutations of a multiset
admits a Hamilton path
if and only if
it is trivial or there are at least two elements in the multiset
that occur an odd number of times.
F. Ruskey, A. Williams.
"The Coolest Way to Generate Combinations",
Discrete Mathematics,
Vol.309, pp.5305-5320 (2009).
This article presents a simple algorithm to generate all
combinations (n-bit strings) by prefix rotations.
Jacqueline M. Smith-Autard.
Dance Composition:
A practical guide to creative success in dance making.
Methuen Drama, A&C Black Publishers, 2010.
The accompanying CD has a nice duo,
showing various elegant ways for a pair to trade places.
Selected quotes
