Asymptotics of the Longest Increasing Subsequence in Random Permutations
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908622887321600 |
|---|---|
| author | Gupta, Mihir |
| author_facet | Gupta, Mihir |
| contents | In this paper, we examine the asymptotic behavior of the longest increasing subsequence (LIS) in a uniformly random permutation of $n$ elements. We rely on the Robinson--Schensted--Knuth correspondence, Young tableaux, and key classical results -- including the Erdős--Szekeres theorem and the Hook Length Formula -- to demonstrate that the expected LIS length grows as $2\sqrt{n}$. We review the essential variational principles of Logan--Shepp and Vershik--Kerov, which determine the limiting shape of the associated random Young diagrams, and summarize the Baik--Deift--Johansson theorem that links fluctuations of the LIS length to the Tracy--Widom distribution. Our approach focuses on providing conceptual and intuitive explanations of these results, unifying classical proofs into a single narrative and supplying fresh visual examples, while referring the reader to the original literature for detailed proofs and rigorous arguments. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_00009 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Asymptotics of the Longest Increasing Subsequence in Random Permutations Gupta, Mihir History and Overview Combinatorics In this paper, we examine the asymptotic behavior of the longest increasing subsequence (LIS) in a uniformly random permutation of $n$ elements. We rely on the Robinson--Schensted--Knuth correspondence, Young tableaux, and key classical results -- including the Erdős--Szekeres theorem and the Hook Length Formula -- to demonstrate that the expected LIS length grows as $2\sqrt{n}$. We review the essential variational principles of Logan--Shepp and Vershik--Kerov, which determine the limiting shape of the associated random Young diagrams, and summarize the Baik--Deift--Johansson theorem that links fluctuations of the LIS length to the Tracy--Widom distribution. Our approach focuses on providing conceptual and intuitive explanations of these results, unifying classical proofs into a single narrative and supplying fresh visual examples, while referring the reader to the original literature for detailed proofs and rigorous arguments. |
| title | Asymptotics of the Longest Increasing Subsequence in Random Permutations |
| topic | History and Overview Combinatorics |
| url | https://arxiv.org/abs/2511.00009 |