Abstract
Given integers k >= 2 and a_1,...,a_k >= 1, let a:= (a_1,...,a_k) and n:= a_1+...+a_k. An a-multiset permutation is a string of length n that contains exactly a_i symbols i for each i=1,...,k.
In this work we consider the problem of exhaustively generating all a-multiset permutations by star transpositions, that is, in each step, the first entry of the string is transposed with any other entry distinct from the first one. This is a far-ranging generalization of several known results.
For example, it is known that permutations (a_1=...=a_k=1) can be generated by star transpositions, while combinations (k=2) can be generated by these operations if and only if they are balanced (a_1=a_2), with the positive case following from the middle levels theorem. To understand the problem in general, we introduce a parameter Delta(a):= n-2max{a_1,...,a_k} that allows us to distinguish three different regimes for this problem.
We show that if Delta(a)0, assuming that they exist for the case Delta(a)=0. For the case Delta(a)=0 we present some partial positive results.
Our proofs establish Hamilton-connectedness or Hamilton-laceability of the underlying flip graphs, and they answer several cases of a recent conjecture of Shen and Williams. In particular, we prove that the middle levels graph is Hamilton-laceable.