Universal cycles for weak orders

DOI10.1137/120886807zbMATH Open1292.05011arXiv1203.5169OpenAlexW2964340647MaRDI QIDQ2870511FDOQ2870511

Authors: Victoria Horan, Glenn H. Hurlbert 

Publication date: 21 January 2014

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Universal cycles are generalizations of de Bruijn cycles and Gray codes that were introduced originally by Chung, Diaconis, and Graham in 1990. They have been developed by many authors since, for various combinatorial objects such as strings, subsets, permutations, partitions, vector spaces, and designs. One generalization of universal cycles, which require almost complete overlap of consecutive words, is s-overlap cycles, which relax such a constraint. In this paper we study weak orders, which are relations that are transitive and complete. We prove the existence of universal and s-overlap cycles for weak orders, as well as for fixed height and/or weight weak orders, and apply the results to cycles for ordered partitions as well.

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

Recommendations

• Efficient universal cycle constructions for weak orders
• Greedy universal cycle constructions for weak orders
• Universal cyclically ordered sets
• Universal cycles for permutation classes
• Universal cycles for permutations
• Universal cycles for combinatorial structures
• On extended cyclic orders
• Extendability of cyclic orders
• On universal cycles for new classes of combinatorial structures
• On extensions of cyclic orders

zbMATH Keywords

universal cyclesweak ordersoverlap cyclespermutation with ties

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Other designs, configurations (05B30) Combinatorics on words (68R15)

Cited In (12)

• A universal cycle for strings with fixed-content (which are also known as multiset permutations)
• The lexicographically smallest universal cycle for binary strings with minimum specified weight
• Universal and overlap cycles for posets, words, and juggling patterns
• Graph universal cycles of combinatorial objects
• Constructing the first (and coolest) fixed-content universal cycle
• 1-overlap cycles for Steiner triple systems
• \(s\)-overlap cycles for permutations
• Greedy universal cycle constructions for weak orders
• Efficient universal cycle constructions for weak orders
• Universal Cycles of Discrete Functions
• Universal cycle packings and coverings for \(k\)-subsets of an \(n\)-set
• Shortened universal cycles for permutations

This page was built for publication: Universal cycles for weak orders

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