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 $$\underset{j=1,...,k}{max}|\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.