Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.19293 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916863817023488 |
|---|---|
| author | Lauff, Robert Tiemens, Lucca |
| author_facet | Lauff, Robert Tiemens, Lucca |
| contents | 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\ge5$ and a $3$-rainbow cycle for odd $n\ge3$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_19293 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Balanced Gray Codes for Permutations and Rainbow Cycles for Associahedra Lauff, Robert Tiemens, Lucca Combinatorics 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\ge5$ and a $3$-rainbow cycle for odd $n\ge3$. |
| title | Balanced Gray Codes for Permutations and Rainbow Cycles for Associahedra |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2507.19293 |