Shortened universal cycles for permutations

DOI10.1016/J.DAM.2022.09.026MaRDI QIDQ2097185zbMATH OpenOpenAlexFDO

Authors Rachel Kirsch, Bernard Lidický, Clare Sibley, Elizabeth Sprangel

Publication date 11 November 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2204.02910

zbMATH Keywords

compressionpermutationuniversal cycles

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorics on words (68R15)

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 $iin[(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 $iin[(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.

Recommendations

• Shorthand universal cycles for permutations
• Universal cycles for permutations
• Faster generation of shorthand universal cycles for permutations
• Universal cycles for permutation classes
• A new universal cycle for permutations
• On shortening u-cycles and u-words for permutations
• Enumerations of universal cycles for \(k\)-permutations
• On a greedy algorithm to construct universal cycles for permutations
• Universal cycles of k-subsets and k-permutations
• Equivalence class universal cycles for permutations

Cites work

• s-overlap cycles for permutations
• A new universal cycle for permutations
• A Successor Rule Framework for Constructing $k$ -Ary de Bruijn Sequences and Universal Cycles
• An explicit universal cycle for the (n-1)-permutations of an n-set
• Graph universal cycles of combinatorial objects
• On a greedy algorithm to construct universal cycles for permutations
• On shortening u-cycles and u-words for permutations
• On universal cycles of labeled graphs
• On universal partial words
• Shorthand universal cycles for permutations
• Universal cycles for combinatorial structures
• Universal cycles for permutations
• Universal cycles for weak orders
• Universal cycles of k-subsets and k-permutations
• Universal partial words over non-binary alphabets

Cited in

(11)

• Universal cycles for permutations
• Universal layered permutations
• A new universal cycle for permutations
• On shortening u-cycles and u-words for permutations
• A construction of short sequences containing all permutations of a set as subsequences
• scientific article; zbMATH DE number 1811347 (Why is no real title available?)
• scientific article; zbMATH DE number 7283890 (Why is no real title available?)
• Graph universal cycles: compression and connections to universal cycles
• Periods of strongly connected multivariate digraphs
• Universal partial tori
• On shortening universal words for multi-dimensional permutations

This page was built for publication: Shortened universal cycles for permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2097185)