On the Distribution of the Length of the Longest Increasing Subsequence of Random Permutations

Jinho Baik; Kurt Johansson; Percy Deift

RECORD

On the Distribution of the Length of the Longest Increasing Subsequence of Random Permutations

Jinho Baik, Percy Deift, Kurt Johansson

Combinatorics · Submitted 16 Oct 1998

abstract compiled · 2026-09-23 · no language-model review

The authors' main claim The main result in this paper is a proof that the distribution function for $l_N$, suitably centered and scaled, converges to the Tracy-Widom distribution [TW1] of the largest eigenvalue of a random GUE matrix.

how it is stated · asserted 1.00 read the record →

Comment (0) Read on arXiv ↗

Cite ▾

arXiv IDmath/9810105 (version 2)

Pith IDXY6L6RSA, Pith's permanent record of this paper and its review

CitationJinho Baik, Kurt Johansson, Percy Deift. "On the Distribution of the Length of the Longest Increasing Subsequence of Random Permutations." arXiv:math/9810105 (1998). https://pith.science/paper/XY6L6RSA

Claim paper

The compiled record

The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Open the compiled record

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 4,360 input tokens.

What the abstract itself states, as probabilities: claims first 0.04 · states limitation 0.12 · human participants 0.01 · controlled comparison 0.02 · randomized assignment 0.02 · states quantitative result 0.29 · compares with prior results 0.18 · mentions code or data availability 0.01.

The abstract, sentence by sentence

arXiv listing abstract v2. Results and the main claim are underlined; show every role.

The authors consider the length, $l_N$, of the length of the longest increasing subsequence of a random permutation of $N$ numbers. The main result in this paper is a proof that the distribution function for $l_N$, suitably centered and scaled, converges to the Tracy-Widom distribution [TW1] of the largest eigenvalue of a random GUE matrix. The authors also prove convergence of moments. The proof is based on the steepest decent method for Riemann-Hilbert problems, introduced by Deift and Zhou in 1993 [DZ1] in the context of integrable systems. The applicability of the Riemann-Hilbert technique depends, in turn, on the determinantal formula of Gessel [Ge] for the Poissonization of the distribution function of $l_N$.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	The authors consider the length, $l_N$, of the length of the longest increasing subsequence of a random permutation of $N$ numbers.	background 0.87	0.56	0.02	asserted 0.85
s1	The main result in this paper is a proof that the distribution function for $l_N$, suitably centered and scaled, converges to the Tracy-Widom distribution [TW1] of the largest eigenvalue of a random GUE matrix.	result 0.97	0.94	0.98	asserted 1.00
s2	The authors also prove convergence of moments.	result 0.94	0.95	0.03	asserted 1.00
s3	The proof is based on the steepest decent method for Riemann-Hilbert problems, introduced by Deift and Zhou in 1993 [DZ1] in the context of integrable systems.	method 0.99	0.14	0.02	asserted 1.00
s4	The applicability of the Riemann-Hilbert technique depends, in turn, on the determinantal formula of Gessel [Ge] for the Poissonization of the distribution function of $l_N$.	method 0.92	0.16	0.02	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 1.00 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v2

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

The paper

Original abstract

The authors consider the length, $l_N$, of the length of the longest increasing subsequence of a random permutation of $N$ numbers. The main result in this paper is a proof that the distribution function for $l_N$, suitably centered and scaled, converges to the Tracy-Widom distribution [TW1] of the largest eigenvalue of a random GUE matrix. The authors also prove convergence of moments. The proof is based on the steepest decent method for Riemann-Hilbert problems, introduced by Deift and Zhou in 1993 [DZ1] in the context of integrable systems. The applicability of the Riemann-Hilbert technique depends, in turn, on the determinantal formula of Gessel [Ge] for the Poissonization of the distribution function of $l_N$.

Human review

How Pith checks papers → · Full audit of this paper →

References

Forward citations

Cited by 4 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

The Hagedorn transition as a Plancherel wall: Tracy-Widom statistics, Polyakov loops and partial deconfinement
hep-th 2026-09 conditional novelty 8.0 of 10

The Hagedorn smoothing coefficient equals the mean of the Tracy-Widom distribution, and the Polyakov loop at the transition is uniformly distributed on a disk of radius one half.
Multicritical Scaling Limit of Shifted Schur Measure
math.CO 2026-05 unverdicted novelty 7.0 of 10

Under multicritical conditions the edge scaling limit of correlations for the shifted Schur measure converges to the higher-order Airy kernel determinant, demonstrating a Pfaffian-to-determinantal transition.
From Yang-Baxter to Robinson-Schensted-Knuth
math.CO 2026-09 accept novelty 4.0 of 10

The Robinson-Schensted-Knuth correspondence is derived from the Yang-Baxter equation via a unique deterministic matching of summands, and its deformations lead to randomized RSK and integrable particle systems.
Lectures on integrable probability
math.PR 2012-12 accept novelty 2.0 of 10

The notes synthesize known integrable-probability results into a mini-course linking random growth, determinantal processes, Schur and Macdonald processes, and directed-polymer asymptotics.

How the literature uses it

39 arXiv papers cite this in 64 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 33 sentences without a confident label

Uses its method or tool 2 papers

Consequently, with these characterizations in terms of bi-orthogonal polynomials and their reproducing kernel, we can employ the Riemann–Hilbert approach to BOPUC [ref] to attain the sought-after asymptotics for multi-bordered, framed, and multi-framed Toeplitz determinants.

Strong Szeg\H{o} Limit Theorems for Multi-Bordered, Framed, and Multi-Framed Toeplitz Determinants · Introduction · 1.00
The same result may also be proved through a more powerful procedure, namely solving a Riemann-Hilbert problem [ref] .

Phase transition in complex-time Loschmidt echo of short and long range spin chain · Determinants of Bessel functions · 0.84

Compares with it 1 paper

Finally, we note that the approach of Baik, Deift and Johansson [ref] for the edge behavior of Plancherel random partitions was based on Riemann-Hilbert techniques, while the approach that we follow here is much closer in spirit to that developed by Borodin, Okounkov and Olshanski [ref] .

The periodic Schur process and free fermions at finite temperature · Conclusion · 0.82

Cites it as support 1 paper

This condition is satisfied with high probability due to arguments such as [ref] about the typical Young diagrams concentrating towards $Θ(√(t))$ rows and columns.

The state hidden subgroup problem and an efficient algorithm for locating unentanglement · The full permutational symmetries defy Fourier sampling · 0.97

Cites it as background 24 papers

Of particular interest is the case $β= 2$ ($$ Tracy-Widom distribution) that initially appeared in the fluctuations of the largest eigenvalue of a $$ random matrix [ref] and that meanwhile exhibited a universal feature in a variety of models: longuest increasing subsequence of a random uniform permutation [ref] , last passage percolation [ref] , log-Gamma polymer partition function [ref] , asymmetric simple exclusion process [ref] , value in $0$ of the Hopf-Cole solution to the KPZ equation [ref] , O'Connell-Yor semidiscrete directed polymer partition function [ref] , etc.

Remarkable structures in integrable probability, I: max-independence structures · Motivations · 0.95
Moreover, as shown by Baik, Deift, and Johansson [ref] , Borodin, Okounkov, and Olshanski [ref] and Johansson [ref] , the edge scaling limit of the random permutations and the Plancherel measure yields the Tracy-Widom distribution, originally introduced to describe the fluctuation of the largest eigenvalue of the Gaussian Unitary Ensemble [ref] .

Multicritical Scaling Limit of Shifted Schur Measure · Introduction · 0.88
The RSK was first applied in this context by Johansson [ref] and Baik–Deift–Johansson [ref] , and the dynamical perspective has been substantially developed by O'Connell [ref] , [ref] , [ref] , Biane–Bougerol–O'Connell [ref] (see also Chhaibi [ref] ), Corwin–O'Connell–Seppäläinen–Zygouras [ref] , O'Connell–Pei [ref] , see also O'Connell–Seppäläinen–Zygouras [ref] .

Nearest neighbor Markov dynamics on Macdonald processes · Introduction · 0.95

Discussion

Know something about this paper? Leave a comment, or highlight any passage above to comment on it.