Permutations and beta-shifts - Mathematics > CombinatoricsReport as inadecuate

Permutations and beta-shifts - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

Abstract: Given a real number beta>1, a permutation pi of length n is realized by thebeta-shift if there is some x in 0,1 such that the relative order of thesequence x,fx,

.,f^{n-1}x, where fx is the factional part of beta*x, isthe same as that of the entries of pi. Widely studied from such diverse fieldsas number theory and automata theory, beta-shifts are prototypical examplesone-dimensional chaotic dynamical systems. When beta is an integer,permutations realized by shifts where studied in SIAM J. Discrete Math. 232009, 765-786. In this paper we generalize some of the results to arbitrarybeta-shifts. We describe a method to compute, for any given permutation pi, thesmallest beta such that pi is realized by the beta-shift. We also give a way todetermine the length of the shortest forbidden i.e., not realized pattern ofan arbitrary beta-shift.

Author: Sergi Elizalde


Related documents