Random permutations and growth models

Let \$\sigma \in S_n\$ be a permutation of the set \$\{1,2,...,n\}\$. The length of the longest increasing subsequence of

\$\sigma\$ is the largest \$k\$ such that there exists a subsequence \$i_1< i_2 <  \dots <i_k\$ with

\$\sigma(i_1)<\sigma(i_2) <  \dots <\sigma(i_k)\$. We will show that \$k\$ is typically of order \$\sqrt{n}\$. We will also

discuss geometric quantities such as the maximum deviation from the diagonal $$\max_{j=1,...,k}|\sigma(i_j)-i_j|.$$

Finally we will see how this model has connections with random matrix theory and how it fits in a wider class of

growth models called the Kardar-Parisi-Zhang universality class.