Decomposing simple permutations, with enumerative consequences (Q2377669)

An interval in the permutation \(\pi\) is a set of contiguous indices \(I=[a,b]\) such that the set of values \(\pi (I)=\{\pi (i):i\in I\}\) also forms an interval of natural numbers. Every permutation \(\pi\) of \([n]=\{1,2,\ldots ,n\}\) has intervals of size 0,1, and \(n\); \(\pi\) is said to be simple if it has no other intervals. The main result of this paper is the following: There is a function \(f(k)\) such that every simple permutation of length at least \(f(k)\) contains two simple subsequences, each of length at least \(k\), sharing at most two entries. Its proof gives a function \(f\) of order about \(k^{k}\). It is shown how this result has enumerative consequences. For example, it implies that, for any \(r\), the number of permutations with at most \(r\) copies of 132 has an algebraic generating function (this was previously proved, constructively, by \textit{M. Bóna} [Adv. Appl. Math. 18, No. 4, 510-522 (1997; Zbl 0879.05006)] and independently, by \textit{T. Mansour and A. Vainshtein} [Adv. Appl. Math. 28, No. 2, 185-195 (2002; Zbl 1005.05001)]. Applications to graph theory and convex geometry are also proposed.