On shortening universal words for multi-dimensional permutations
Discrete Mathematics · 2026-08 · 349 (8) · 115081
DOI: 10.1016/j.disc.2026.115081 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Mathematics, 2026-08. Verfasst von Sergey Kitaev und 1 weiteren Autor:innen. Die Arbeit nennt 17 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Natural Science Foundation of China, Natural Science Foundation of Tianjin Municipality, Fundamental Research Funds for the Central Universities.
Abstract (Originalsprache)
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$).
Förderung
- National Natural Science Foundation of China
- Natural Science Foundation of Tianjin Municipality
- Fundamental Research Funds for the Central Universities
- Leverhulme Trust
Zitieren
APA
Kitaev, S., & Qiu, D. (2026). On shortening universal words for multi-dimensional permutations. Discrete Mathematics, 349(8), 115081. https://doi.org/10.1016/j.disc.2026.115081
Vancouver
Kitaev S, Qiu D. On shortening universal words for multi-dimensional permutations. Discrete Mathematics. 2026;349(8):115081. doi:10.1016/j.disc.2026.115081
BibTeX
@article{Kitaev2026,
author = {Kitaev, Sergey and Qiu, Dun},
title = {On shortening universal words for multi-dimensional permutations},
journal = {Discrete Mathematics},
year = {2026},
volume = {349},
number = {8},
pages = {115081},
doi = {10.1016/j.disc.2026.115081}
}
EUVIMED