Increasing subsequences of linear size in random permutations and the Robinson-Schensted tableaux of permutons

Abstract

The study of longest increasing subsequences (LIS) in permutations led to that of Young diagrams via Robinson-Schensted's (RS) correspondence. In a celebrated paper, Vershik and Kerov obtained a limit theorem for such diagrams and found that the LIS of a uniform permutation of size n behaves as $2\sqrt{n}$. Independently and much later, Hoppen et al. introduced the theory of permutons as a scaling limit of permutations. In this paper, we extend in some sense the RS correspondence of permutations to the space of permutons. When the "RS-tableaux" of a permuton are non-trivial, we show that the RS-tableaux of random permutations sampled from this permuton exhibit a linear behavior, in the sense that their first rows and columns have lengths of linear order. In particular, the LIS of such permutations behaves as a multiple of n. We also prove some large deviation results for these convergences. Finally, by studying asymptotic properties of Fomin's algorithm for permutations, we show that the RS-tableaux of a permuton satisfy a partial differential equation.

arXiv comment39 pages. Revised version, accepted for publication in Random Structures & Algorithms

References in corpus (10)

• Fixed points and cycle structure of random permutations
• Robinson-Schensted-Knuth algorithm, jeu de taquin and Kerov-Vershik measures on infinite tableaux
• Square permutations are typically rectangular
• Independent sets, cliques, and colorings in graphons
• Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
• Graphons, permutons and the Thoma simplex: three mod-Gaussian moduli spaces
• The skew Brownian permuton: a new universality class for random constrained permutations
• Random Permutations -- A geometric point of view
• Locally uniform random permutations with large increasing subsequences
• A note on limits of sequences of binary trees

Cited by in corpus (2)

• Locally uniform random permutations with large increasing subsequences
• Binary search trees of permuton samples