Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [3 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184447
Contributor : Coordination Episciences Iam <>
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

Identifiers

  • HAL Id : hal-01184447, version 1

Collections

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. ⟨hal-01184447⟩

Share

Metrics

Record views

403

Files downloads

1785