Discrete mathematics and mathematical cybernetics

Antimonotone permutations

M. A. Makarov

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk

Abstract: The paper is devoted to a class of infinite permutations. One of the properties of these permutations is their avoiding monotone subsequences of elements with numbers forming an arithmetical progression of length 3. We find the complexity of these permutations, their Rauzy graphs, their maximal pattern complexity, their arithmetical complexity with odd differences, and also we find the lower and upper bounds for their arithmetical complexity and show that these bounds are attained.

Keywords: infinite permutations, combinatorics on words, Rauzy graphs, maximal pattern complexity, arithmetical complexity.

UDC: 519.1

MSC: 68R05

Received May 26, 2012, published July 30, 2012