Increasing subsequences of linear size in random permutations and the Robinson-Schensted tableaux of permutons
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915069522083840 |
|---|---|
| author | Dubach, Victor |
| author_facet | Dubach, Victor |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_05768 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Increasing subsequences of linear size in random permutations and the Robinson-Schensted tableaux of permutons Dubach, Victor Probability Combinatorics 60C05, 05A05 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. |
| title | Increasing subsequences of linear size in random permutations and the Robinson-Schensted tableaux of permutons |
| topic | Probability Combinatorics 60C05, 05A05 |
| url | https://arxiv.org/abs/2307.05768 |