Abstract

Given integers k >= 2 $k\ge 2$ and a1, horizontal ellipsis ,ak >= 1 ${a}_{1},\ldots ,{a}_{k}\ge 1$, let a colon equals (a1, horizontal ellipsis ,ak) ${\boldsymbol{a}}:= ({a}_{1},\ldots ,{a}_{k})$ and n colon equals a1+MIDLINE HORIZONTAL ELLIPSIS+ak $n:= {a}_{1}+\cdots \,\,+{a}_{k}$. An a-multiset permutation is a string of length n $n$ that contains exactly ai ${a}_{i}$ symbols i $i$ for each i=1, horizontal ellipsis ,k $i=1,\ldots ,k$. In this work we consider the problem of exhaustively generating all a ${\boldsymbol{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 (a1=MIDLINE HORIZONTAL ELLIPSIS=ak=1 ${a}_{1}=\cdots \,={a}_{k}=1$) can be generated by star transpositions, while combinations (k=2 $k=2$) can be generated by these operations if and only if they are balanced (a1=a2 ${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) colon equals n-2max{a1, horizontal ellipsis ,ak} ${\rm{\Delta }}({\boldsymbol{a}}):= n-2\max \{{a}_{1},\ldots ,{a}_{k}\}$ that allows us to distinguish three different regimes for this problem. We show that if Delta(a)<0 ${\rm{\Delta }}({\boldsymbol{a}})\lt 0$, then a star transposition Gray code for a-multiset permutations does not exist. We also construct such Gray codes for the case Delta(a)>0 ${\rm{\Delta }}({\boldsymbol{a}})\gt 0$, assuming that they exist for the case Delta(a)=0 ${\rm{\Delta }}({\boldsymbol{a}})=0$. For the case Delta(a)=0 ${\rm{\Delta }}({\boldsymbol{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.