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

Victor Dubach

Published 2023-07-11Version 1

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 established a limit theorem for such diagrams and deduced the $2\sqrt{n}$ estimate for the LIS of a uniformly random permutation of size $n$. Independently, 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-zero we obtain a linear behavior for the sampled permutations' RS-tableaux, along with some large deviation results. In particular, the LIS of sampled permutations behaves as a multiple of $n$. 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.