Universal cycles for permutations

DOI10.1016/J.DISC.2007.11.004MaRDI QIDQ1044883zbMATH OpenOpenAlexFDO

Authors J. Robert Johnson

Publication date 15 December 2009

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

permutationsuniversal cyclescombinatorial generation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Abstract: A universal cycle for permutations is a word of length n! such that each of the n! possible relative orders of n distinct integers occurs as a cyclic interval of the word. We show how to construct such a universal cycle in which only n+1 distinct integers are used. This is best possible and proves a conjecture of Chung, Diaconis and Graham.

Recommendations

• Universal cycles for permutation classes
• Shortened universal cycles for permutations
• Universal cycles for combinatorial structures
• Enumerations of universal cycles for \(k\)-permutations
• On shortening \(u\)-cycles and \(u\)-words for permutations

Cites work

• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• Shorthand universal cycles for permutations
• Universal cycles for combinatorial structures
• Universal cycles of \(k\)-subsets and \(k\)-permutations

Cited in

(39)

• Shortened universal cycles for permutations
• Generalized de Bruijn words for primitive words and powers
• Graph universal cycles of combinatorial objects
• Constructing the first (and coolest) fixed-content universal cycle
• Universal cycles for combinatorial structures
• Solution of an outstanding conjecture: the non-existence of universal cycles with \(k=n-2\)
• A universal cycle for strings with fixed-content (which are also known as multiset permutations)
• A new universal cycle for permutations
• scientific article; zbMATH DE number 4173894 (Why is no real title available?)
• Shorthand universal cycles for permutations
• Enumerating cycles in the graph of overlapping permutations
• An explicit universal cycle for the \((n-1)\)-permutations of an \(n\)-set
• Efficient universal cycle constructions for weak orders
• Supertrees
• The lexicographically smallest universal cycle for binary strings with minimum specified weight
• Enumerations of universal cycles for \(k\)-permutations
• Containing all permutations
• Generalizing the classic greedy and necklace constructions of de Bruijn sequences and universal cycles
• Universal cycles of classes of restricted words
• Gray codes and symmetric chains
• Universal Cycles for Weight-Range Binary Strings
• Universal cycles of complementary classes
• On a greedy algorithm to construct universal cycles for permutations
• Gray codes and symmetric chains
• Graph universal cycles: compression and connections to universal cycles
• Universal Cycles of Discrete Functions
• Universal traversal sequences for paths and cycles
• The feasible region for consecutive patterns of permutations is a cycle polytope
• Universal cycles for permutation classes
• scientific article; zbMATH DE number 1811347 (Why is no real title available?)
• Faster generation of shorthand universal cycles for permutations
• Sparse Kneser graphs are Hamiltonian
• Universal cycle packings and coverings for \(k\)-subsets of an \(n\)-set
• On shortening \(u\)-cycles and \(u\)-words for permutations
• On a family of universal cycles for multi-dimensional permutations
• Universal and overlap cycles for posets, words, and juggling patterns
• Universal cycles for weak orders
• The feasible region for consecutive patterns of permutations is a cycle polytope
• Euler tours in hypergraphs

This page was built for publication: Universal cycles for permutations

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