On shortening universal words for multi-dimensional permutations
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914361477431296 |
|---|---|
| author | Kitaev, Sergey Qiu, Dun |
| author_facet | Kitaev, Sergey Qiu, Dun |
| contents | A universal word (u-word) for $d$-dimensional permutations of length $n$ is a 2-dimensional word with $d-1$ rows, any size $n$ window of which is order-isomorphic to exactly one permutation of length $n$, and all permutations of length $n$ are covered. It is known that u-words (in fact, even u-cycles, a stronger claim) for $d$-dimensional permutations exist.
In this paper, we use the idea of incomparable elements to prove that u-words of length $(n!)^{d-1}+n-1-i(n-1)$, for $d\geq 2$ and $$0\leq i\leq \frac{2^{d-1}}{n-1}\left[(1+(n-1)!)^{d-1}-\left(1+\frac{(n-1)!}{2}\right)^{d-1}\right],$$ for $d$-dimensional permutations of length $n$ exist, which generalizes the respective result of Kitaev, Potapov and Vajnovszki for ``usual'' permutations ($d=2$). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_01005 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On shortening universal words for multi-dimensional permutations Kitaev, Sergey Qiu, Dun Combinatorics A universal word (u-word) for $d$-dimensional permutations of length $n$ is a 2-dimensional word with $d-1$ rows, any size $n$ window of which is order-isomorphic to exactly one permutation of length $n$, and all permutations of length $n$ are covered. It is known that u-words (in fact, even u-cycles, a stronger claim) for $d$-dimensional permutations exist. In this paper, we use the idea of incomparable elements to prove that u-words of length $(n!)^{d-1}+n-1-i(n-1)$, for $d\geq 2$ and $$0\leq i\leq \frac{2^{d-1}}{n-1}\left[(1+(n-1)!)^{d-1}-\left(1+\frac{(n-1)!}{2}\right)^{d-1}\right],$$ for $d$-dimensional permutations of length $n$ exist, which generalizes the respective result of Kitaev, Potapov and Vajnovszki for ``usual'' permutations ($d=2$). |
| title | On shortening universal words for multi-dimensional permutations |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2603.01005 |