Universal cycles for weak orders

DOI10.1137/120886807MaRDI QIDQ2870511zbMATH OpenOpenAlexFDO

Authors Victoria Horan, Glenn H. Hurlbert

Publication date 21 January 2014

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

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

zbMATH Keywords

overlap cyclespermutation with tiesuniversal cyclesweak orders

Mathematics Subject Classification ID

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

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.

Review text

Given a set \({\mathcal C}\) of strings, all of the same length, a universal cycle (ucycle) is a cyclic word that contains each element of the set \({\mathcal C}\) exactly once. Examples of ucycles include de Bruijn cycles and Gray codes, first introduced by \textit{F. Chung} et al. [Discrete Math. 110, No. 1--3, 43--59 (1992; Zbl 0776.05001)]. A further generalization of the notion of a ucycle is the notion of an \(s\)-overlap cycle, first introduced in [\textit{A. P. Godbole} et al., Congr. Numerantium 204, 161--171 (2010; Zbl 1229.05104)]. This paper studies weak orders, defined as transitive and complete relations. The authors prove the existence of universal and \(s\)-overlap cycles for weak orders, as well as for weight orders of fixed height or weight.

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

Cited in

(13)

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