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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Star Transposition Gray Codes for Multiset Permutations with Uniform Frequency

Ariel Elboim
Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
preprint

Star Transposition Gray Codes for Multiset Permutations with Uniform Frequency

Ariel Elboim
preprint en

Abstract

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.

Zenodo (CERN European Organization for Nuclear Research)
Advanced Combinatorial Mathematics
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon