Star transposition Gray codes for multiset permutations.

Given integers k≥2 $k\ge 2$ and a1,...,ak≥1 ${a}_{1},\ldots ,{a}_{k}\ge 1$, let a≔(a1,...,ak) ${\boldsymbol{a}}:= ({a}_{1},\ldots ,{a}_{k})$ and n≔a1+⋯+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,...,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=⋯=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 Δ(a)≔n−2max{a1,...,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 Δ(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 Δ(a)>0 ${\rm{\Delta }}({\boldsymbol{a}})\gt 0$, assuming that they exist for the case Δ(a)=0 ${\rm{\Delta }}({\boldsymbol{a}})=0$. For the case Δ(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. [ABSTRACT FROM AUTHOR]