# 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 :
Document type :
Conference papers
Domain :

Cited literature [3 references]

https://hal.inria.fr/hal-01184447
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, August 14, 2015 - 2:59:22 PM
Last modification on : Friday, October 13, 2017 - 8:08:02 PM
Long-term archiving on: : Sunday, November 15, 2015 - 11:13:48 AM

### File

dmAE0153.pdf
Publisher files allowed on an open archive

### Citation

Dmitri G. Fon-Der-Flaass, Anna E. Frid. On infinite permutations. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.267-272, ⟨10.46298/dmtcs.3458⟩. ⟨hal-01184447⟩

Record views