Erdős–Szekeres permutations and square Young tableaux
Dan Romik · Cambridge University Press eBooks · 2014
Chapter summary . We continue our study of longest increasing subsequences in permutations by considering a special class of permutations called Erdőos-Szekeres permutations , which have the property that their longest monotone subsequence is the shortest possible and are thus extremal cases demonstrating sharpness in the Erdőos-Szekeres theorem. These permutations are related via the Robinson-Schensted correspondence to an especially well-behaved class of standard Young tableaux, the square Young tableaux . We use the tools developed in Chapter 1 to analyze the behavior of random square Young tableaux, and this leads us to an interesting result on the limiting shape of random Erdőos-Szekeres permutations. We also find a mysterious arctic circle that appears when we interpret some of the results as describing the asymptotic behavior of a certain interacting particle system . Erdős–Szekeres permutations In the previous two chapters we studied the statistical behavior of the permutation statistic L ( σ ) for a typical permutation σ chosen at random from among all permutations of given order. In this chapter we focus our attention instead on those permutations σ whose behavior with regard to longest increasing subsequences, or more precisely longest monotone subsequences, is atypical in the most extreme way possible. We refer to these permutations as Erdős–Szekeres permutations , because of their role as extremal cases demonstrating the sharpness in the Erdős-Szekeres theorem (Theorem 1.2).