Michael Albert ; Julian West - Universal cycles for permutation classes

dmtcs:2727 - Discrete Mathematics & Theoretical Computer Science, January 1, 2009, DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) - https://doi.org/10.46298/dmtcs.2727
Universal cycles for permutation classesArticle

Authors: Michael Albert 1; Julian West 2

  • 1 Department of Computer Science, University of Otago
  • 2 Dept. of Mathematics, University of Victoria

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$.


Volume: DMTCS Proceedings vol. AK, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)
Section: Proceedings
Published on: January 1, 2009
Imported on: January 31, 2017
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]

3 Documents citing this article

Consultation statistics

This page has been seen 279 times.
This article's PDF has been downloaded 227 times.