Balanced Gray Codes for Permutations and Rainbow Cycles for Associahedra

Abstract

We settle the problem of constructing a balanced transposition Gray code for permutations of $[n]:=\{1,\dots ,n\}$ with $n\in \mathbb{N}\setminus \{0\}$. More generally, we obtain a~$2(m-2)!$-rainbow cycle for the permutations of $[n]$ for $m\in [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 ${\mathcal{A}}_n$ for $k\in [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 $P_n$ admits a $2$-rainbow cycle for all $n\ge 5$ and a $3$-rainbow cycle for odd $n\ge 3$.

34 pages, 15 figures