The longest increasing subsequence in a random permutation and a unitary random matrix model
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.
scientific article; zbMATH DE number 1187585