Universal cycles for permutations

DOI10.1016/J.DISC.2007.11.004zbMATH Open1181.05005arXiv0710.5611OpenAlexW2100731258MaRDI QIDQ1044883FDOQ1044883

Authors: J. Robert Johnson 

Publication date: 15 December 2009

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

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.

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

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

zbMATH Keywords

permutationsuniversal cyclescombinatorial generation

Mathematics Subject Classification ID

Permutations, words, matrices (05A05)

Cites Work

• Title not available (Why is that?)
• Universal cycles for combinatorial structures
• Universal cycles of \(k\)-subsets and \(k\)-permutations
• Shorthand universal cycles for permutations

Cited In (39)

• Universal cycles of complementary classes
• Title not available (Why is that?)
• 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
• On shortening \(u\)-cycles and \(u\)-words for permutations
• Title not available (Why is that?)
• Universal cycles of classes of restricted words
• Generalizing the classic greedy and necklace constructions of de Bruijn sequences and universal cycles
• The feasible region for consecutive patterns of permutations is a cycle polytope
• 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
• Sparse Kneser graphs are Hamiltonian
• Shorthand universal cycles for permutations
• Containing all permutations
• Universal cycles for combinatorial structures
• On a family of universal cycles for multi-dimensional permutations
• The feasible region for consecutive patterns of permutations is a cycle polytope
• Generalized de Bruijn words for primitive words and powers
• Graph universal cycles: compression and connections to universal cycles
• Universal traversal sequences for paths and cycles
• Solution of an outstanding conjecture: the non-existence of universal cycles with \(k=n-2\)
• Universal Cycles for Weight-Range Binary Strings
• An explicit universal cycle for the ( n -1)-permutations of an n -set
• Gray codes and symmetric chains
• Gray codes and symmetric chains
• Supertrees
• Euler tours in hypergraphs
• Enumerating cycles in the graph of overlapping permutations
• Efficient universal cycle constructions for weak orders
• Universal Cycles of Discrete Functions
• Universal cycle packings and coverings for \(k\)-subsets of an \(n\)-set
• A new universal cycle for permutations
• Faster generation of shorthand universal cycles for permutations
• Universal cycles for permutation classes
• Universal cycles for weak orders
• On a greedy algorithm to construct universal cycles for permutations
• Shortened universal cycles for permutations
• Enumerations of universal cycles for \(k\)-permutations

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)