On the distributions of the lengths of the longest monotone subsequences in random words

1999/04/30 by Craig A. Tracy, Harold Widom · 4 citations
Mathematics · Physics and Astronomy · #Advanced Algebra and Geometry #Advanced Combinatorial Mathematics #Random Matrices and Applications #math.CO #math.PR #msc:05A15 #msc:47B35 #msc:60C05 #msc:82B23 #nlin.SI #solv-int

paper · pdf · doi:10.1007/pl00008763

published as Probab. Theory Relat. Fields 119 (2001), 350-380 · 30 pages, revised version corrects an error in the statement of Theorem 4

arxiv created 1999/07/01 · openalex publication_date 2001/03/01 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the distributions of the lengths of the longest weakly increasing and strongly decreasing subsequences in words of length N from an alphabet of k letters. We find Toeplitz determinant representations for the exponential generating functions (on N) of these distribution functions and show that they are expressible in terms of solutions of Painlevé V equations. We show further that in the weakly increasing case the generating function gives the distribution of the smallest eigenvalue in the k x k Laguerre random matrix ensemble and that the distribution itself has, after centering and normalizing, an N -> infinity limit which is equal to the distribution function for the largest eigenvalue in the Gaussian Unitary Ensemble of k x k hermitian matrices of trace zero.

Citations

• Correlation Functions, Cluster Functions, and Spacing Distributions for Random Matrices
• Fredholm determinants, differential equations and matrix models
• Monodromy perserving deformation of linear ordinary differential equations with rational coefficients. II

Cited by

• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• Vicious walkers and hook Young tableaux
• Random matrix theory
• Multiple phases in a generalized Gross-Witten-Wadia matrix model