Dmitri G. Fon-Der-Flaass ; Anna E. Frid - On infinite permutations

dmtcs:3458 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3458
On infinite permutationsArticle

Authors: Dmitri G. Fon-Der-Flaass 1; Anna E. Frid 1

  • 1 Sobolev Institute of Mathematics

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.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: infinite permutation,ordering,periodicity,complexity,subword complexity,Sturmian words,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]

1 Document citing this article

Consultation statistics

This page has been seen 181 times.
This article's PDF has been downloaded 855 times.