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

MaRDI QIDQ6443403zbMATH OpenFDO

Authors

Publication date 11 July 2023

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05)

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 established a limit theorem for such diagrams and deduced the $2sqrtn$ 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.

This page was built for publication: Increasing subsequences of linear size in random permutations and the Robinson-Schensted tableaux of permutons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6443403)