Abstrakt
Given integers k >= 2 and a1, . . ., ak >= 1, let a := (a1, . . ., ak) and n := a1 + . . . + ak. An a-multiset permutation is a string of length n that contains exactly ai symbols i for each i = 1, . . ., k.
In this work we consider the problem of exhaustively generating all a-multiset permutations by star transpositions, i.e., 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 (a1 = . . . = ak = 1) can be generated by star transpositions, while combinations (k = 2) can be generated by these operations if and only if they are balanced (a1 = a2), with the positive case following from the middle levels theorem. To understand the problem in general, we introduce a parameter Delta(a):= n - 2 max{a1, . . ., ak} 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 INCREMENT (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.