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