Star Transposition Gray Codes for Multiset Permutations with Uniform Frequency
Shen and Williams conjectured that words of equal symbol counts can be listed in a cycle by swapping the leading symbol with a different symbol. Earlier authors treated two symbols, one copy per symbol, and common counts 2, 3, 4. Theorem T (ARGUED †) gives the listing for every common count c ≥ 1 and every number k ≥ 2 of symbols, counting the single edge for c = 1, k = 2 as cyclic. The dagger marks dependence on finite computational checks. No human referee has checked the proofs. When one symbol fills half the word, treat its slots as empty and mark every other slot with a token that carries its original symbol as a colour. This gives the binary middle-levels graph. Restoring the token colours lifts a Hamilton cycle of that graph to one or more circuits, which we join. We then cut the resulting cycles into spanning paths with specified ends. By fixing one or two positions after the leading symbol, we join shorter paths by induction on word length. Closing a spanning path along an edge gives the cyclic listing. The argument uses finite checks for half-lengths 3 ≤ m ≤ 8 and for three small path cases.
Authors
- Ariel Elboim (ORCID: https://orcid.org/0009-0001-1341-366X)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-21
- DOI
- https://doi.org/10.5281/zenodo.24417542
- Primary Topic
- Advanced Combinatorial Mathematics
- Type
- preprint