Random permutations and growth models

Christopher Hoffman
-
PDL C-036
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.
Event Type
Event Subcalendar