Universal cycles for permutation classes

Abstract

We define a universal cycle for a class of $n$-permutations as a cyclic word in which each element of the class occurs exactly once as an $n$-factor. We give a general result for cyclically closed classes, and then survey the situation when the class is defined as the avoidance class of a set of permutations of length $3$, or of a set of permutations of mixed lengths $3$ and $4$.

Keywords

• universal cycles
• restricted permutations
• eulerian circuits
• debruijn graphs
• [math.math-co] mathematics [math]/combinatorics [math.co]
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]