Universal cycles for permutations

2007/10/30 by J. Robert Johnson, Johnson, J. Robert
Computer Science · Engineering · Mathematics · #05A99 #Advanced Combinatorial Mathematics #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.0710.5611

openalex publication_date 2007/10/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Related

• On a Greedy Algorithm to Construct Universal Cycles for Permutations
• On a family of universal cycles for multi-dimensional permutations
• On shortening u-cycles and u-words for permutations
• Enumerations of Universal Cycles for k-Permutations
• Universal Cycles of Complementary Classes