Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0932.05001
Baik, Jinho; Deift, Percy; Johansson, Kurt
On the distribution of the length of the longest increasing subsequence of random permutations. (English)
[J] J. Am. Math. Soc. 12, No.4, 1119-1178 (1999). ISSN 0894-0347; ISSN 1088-6834/e

If $\pi(1), \dots, \pi(n)$ is a permutation of $1, \dots, n$, the subsequence $\pi(i_1), \dots, \pi(i_k)$ is increasing if $i_1< \cdots <i_k$ and $\pi(i_1) <\cdots <\pi (i_k)$. Let $l_n$ be the length of the longest increasing subsequence in a random permutation assigning equal probabilities $1/n$! to the permutations. The limiting distribution of $l_n$ is determined, and all moments of $l_n$ are shown to converge to the corresponding moments of the limiting distribution. This limiting distribution is equal to the limiting distribution of the largest eigenvalue of a random Hermitian $n\times n$ matrix $M$ with a probability density proportional to $\exp[-\text{trace}(M^2)]$.
[Ove Frank (Stockholm)]

MSC 2000:: *05A05 Combinatorial choice problems
15A52 Random matrices
33D45 Basic hypergeometric functions and integrals in several variables
45E05 Integral equations with kernels of Cauchy type
60F99 Limit theorems (probability)

Keywords: random permutations; orthogonal polynomials; Riemann-Hilbert problems; random matrices; steepest descent method; limiting distribution; eigenvalue

Cited in: Zbl 1234.60010 Zbl 1119.14002 Zbl 1041.15019 Zbl 1035.82020 Zbl 1033.60006 Zbl 1011.05008 Zbl 1025.82010 Zbl 1011.60085 Zbl 1018.15020 Zbl 0966.60010 Zbl 0963.05133 Zbl 0960.60097 Zbl 0937.60001

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]