DMTCS Proceedings, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009)

Font Size:  Small  Medium  Large

Universal cycles for permutation classes

Michael Albert, Julian West

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.
Résumé. Nous définissons un cycle universel pour une classe de n-permutations comme un mot cyclique dans lequel chaque élément de la classe appara&\i;t une unique fois comme n-facteur. Nous donnons un resultat général pour les classes cycliquement closes, et détaillons la situation où la classe de permutations est définie par motifs exclus, avec des motifs de taille 3, ou bien à la fois des motifs de taille 3 et de taille 4.

Full Text: GZIP Compressed PostScript PostScript PDF

Valid XHTML 1.0 Transitional