Permutations without long decreasing subsequences and random matrices

MaRDI QIDQ870067zbMATH OpenFDO

Authors Piotr Śniady

Publication date 12 March 2007

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0603401, https://eudml.org/doc/127480, http://www.emis.de/journals/EJC/Volume_14/Abstracts/v14i1r11.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

random matrixrandom permutationYoung diagram

Mathematics Subject Classification ID

Combinatorial aspects of representation theory (05E10) Random matrices (algebraic aspects) (15B52) Brownian motion (60J65)

Abstract: 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 oinfty the rows of lambda behave like the eigenvalues of a certain random matrix (traceless Gaussian Unitary Ensemble) 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.

Review text

Summary: 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.

Recommendations

• On the distribution of the length of the longest increasing subsequence of random permutations
• The longest increasing subsequence in a random permutation and a unitary random matrix model
• Permutations with short monotone subsequences
• The asymptotics of monotone subsequences of involutions
• scientific article; zbMATH DE number 1549030

Cited in

(9)

• Random unitary matrices, permutations and Painlevé
• Monotonous subsequences and the descent process of invariant random permutations
• GL(n, q) and increasing subsequences in non-uniform random permutations
• Random permutations and the discrete Bessel kernel
• Permutations with short monotone subsequences
• scientific article; zbMATH DE number 1549030 (Why is no real title available?)
• An asymptotic version of a theorem of Knuth
• Increasing subsequences of linear size in random permutations and the Robinson-Schensted tableaux of permutons
• A Galton-Watson tree approach to local limits of permutations avoiding a pattern of length three

This page was built for publication: Permutations without long decreasing subsequences and random matrices

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