2025/07/25 by Robert Lauff, Lauff, Robert, Lucca Tiemens +1
Biochemistry, Genetics and Molecular Biology · Engineering · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Genome Rearrangement Algorithms #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2507.19293
openalex publication_date 2025/07/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We settle the problem of constructing a balanced transposition Gray code for permutations of [n] := \1, …, n\ with n ∈ ℕ∖\0\. More generally, we obtain a~2(m-2)!-rainbow cycle for the permutations of [n] for m ∈ [n], a notion recently introduced by Felsner, Kleist, Mütze, and Sering. Furthermore, we extend a result of theirs by presenting a k-rainbow cycle for the classical associahedron An for k ∈ [2n + 2]. For even n, we also construct a balanced Gray code for permutations of [n], using only cyclically adjacent transpositions, complementing the construction for odd n by Gregor, Merino, and Mütze. Additionally, we show that the Permutahedron Pn admits a 2-rainbow cycle for all n≥5 and a 3-rainbow cycle for odd n≥3.