# On infinite permutations

Abstract : We define an infinite permutation as a sequence of reals taken up to the order, or, equivalently, as a linear ordering of a finite or countable set. Then we introduce and characterize periodic permutations; surprisingly, for each period $t$ there is an infinite number of distinct $t$-periodic permutations. At last, we introduce a complexity notion for permutations analogous to subword complexity for words, and consider the problem of minimal complexity of non-periodic permutations. Its answer is different for the right infinite and the bi-infinite case.
Keywords :
Type de document :
Communication dans un congrès
Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.267-272, 2005, DMTCS Proceedings
Domaine :
Liste complète des métadonnées

Littérature citée [3 références]

https://hal.inria.fr/hal-01184447
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 14 août 2015 - 14:59:22
Dernière modification le : vendredi 13 octobre 2017 - 20:08:02
Document(s) archivé(s) le : dimanche 15 novembre 2015 - 11:13:48

### Fichier

dmAE0153.pdf
Fichiers éditeurs autorisés sur une archive ouverte

### Identifiants

• HAL Id : hal-01184447, version 1

### Citation

Dmitri G. Fon-Der-Flaass, Anna E. Frid. On infinite permutations. Stefan Felsner. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), pp.267-272, 2005, DMTCS Proceedings. 〈hal-01184447〉

### Métriques

Consultations de la notice

## 379

Téléchargements de fichiers