Permutations without long decreasing subsequences and random matrices
The electronic journal of combinatorics, Tome 14 (2007)
We study the shape of the Young diagram $\lambda$ associated via the Robinson–Schensted–Knuth algorithm to a random permutation in $S_n$ such that the length of the longest decreasing subsequence is not bigger than a fixed number $d$; in other words we study the restriction of the Plancherel measure to Young diagrams with at most $d$ rows. We prove that in the limit $n\to\infty$ the rows of $\lambda$ behave like the eigenvalues of a certain random matrix (namely the traceless Gaussian Unitary Ensemble random matrix) with $d$ rows and columns. In particular, the length of the longest increasing subsequence of such a random permutation behaves asymptotically like the largest eigenvalue of the corresponding random matrix.
DOI :
10.37236/929
Classification :
05E10, 15B52, 60J65
Mots-clés : Young diagram, random permutation, random matrix
Mots-clés : Young diagram, random permutation, random matrix
@article{10_37236_929,
author = {Piotr \v{S}niady},
title = {Permutations without long decreasing subsequences and random matrices},
journal = {The electronic journal of combinatorics},
year = {2007},
volume = {14},
doi = {10.37236/929},
zbl = {1113.05100},
url = {http://geodesic.mathdoc.fr/articles/10.37236/929/}
}
Piotr Šniady. Permutations without long decreasing subsequences and random matrices. The electronic journal of combinatorics, Tome 14 (2007). doi: 10.37236/929
Cité par Sources :