Shortened universal cycles for permutations
Date
2022-04-06
Authors
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
© 2022 The Authors
Abstract
Kitaev, Potapov, and Vajnovszki [On shortening u-cycles and u-words for permutations, Discrete Appl. Math, 2019] described how to shorten universal words for permutations, to length n!+n−1−i(n−1) for any i∈[(n−2)!], by introducing incomparable elements. They conjectured that it is also possible to use incomparable elements to shorten universal cycles for permutations to length n!−i(n−1) for any i∈[(n−2)!]. In this note we prove their conjecture. The proof is constructive, and, on the way, we also show a new method for constructing universal cycles for permutations.
Series Number
Journal Issue
Is Version Of
Article
Shortened universal cycles for permutations
(Elsevier,
2023-01-15)
Kitaev, Potapov, and Vajnovszki [On shortening u-cycles and u-words for permutations, Discrete Appl. Math, 2019] described how to shorten universal words for permutations, to length n!+n−1−i(n−1) for any i ∈ [(n − 2)!], by introducing incomparable elements. They conjectured that it is also possible to use incomparable elements to shorten universal cycles for permutations to length n! − i(n − 1) for any i ∈ [(n − 2)!]. In this note we prove their conjecture. The proof is constructive, and, on the way, we alsoshow a new method for constructing universal cycles for permutations.
Versions
Series
Academic or Administrative Unit
Type
Preprint
Comments
This preprint is made available through arXiv at doi:https://doi.org/10.48550/arXiv.2204.02910.