The longest increasing subsequence in a random permutation and a unitary random matrix model
type: Item
instance of: scholarly article
title: The longest increasing subsequence in a random permutation and a unitary random matrix model
zbMATH Open document ID: 0923.60008
author: Kurt Johansson
published in: Mathematical Research Letters
publication date: 1999-10-17T00:00:00Z
review text: Let \(S_N\) be the group of all permutations of \(\{1, 2, \dots , N\}\). The main results of the paper are two theorems. Theorem 1. If \(F_N(n)\) is the longest increasing subsequence in a random permutation from \(S_N\), then \[ \lim_{N\to \infty} F_N(x\sqrt{N})=\begin{cases} 0,&\text{if } 0\leq x<2,\\ 1, &\text{if } x>2.\end{cases} \] Theorem 2. The expexted length \(L_N\) of the longest increasing subsequence in a random permutation in \(S_N\) satisfies \(\lim_{N\to \infty} L_N/\sqrt{N}= 2.\) A new proof of Theorem 2 based on analytic tools from the theory of random matrices is given.
Mathematics Subject Classification ID: 60B15
Mathematics Subject Classification ID: 05E15
Mathematics Subject Classification ID: 82B26
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 1187585
zbMATH Keywords: random permutation
zbMATH Keywords: longest increasing subsequence
zbMATH Keywords: random matrices
MaRDI profile type: Publication
full work available at URL: mrl.1998.v5.n1.a6
OpenAlex ID: W2083884937
DOI: 10.4310/MRL.1998.V5.N1.A6
description: scientific article; zbMATH DE number 1187585