EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

On shortening universal words for multi-dimensional permutations

Sergey Kitaev, Dun Qiu

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →