Abstract

As a classical problem in combinatorics, consider the longest increasing subsequence of a random permutations of the sequence $1,2,\dots,n$. By a result of Vershik-Kerov and Logan-Shepp , the length of such a random subsequence $L_n$ is approximately $2\sqrt{n}$. Recently Baik, Deift and Johansson settled a long standing open problem by showing that the fluctuations of $L_n$ is of order $n^{1/6}$. In these lectures, I explain how probabilistic arguments can be used to study $L_n$. After the work of Hammerseley and Aldous-Diaconis, a random growth process known as Hammersely model is used to get insight into the behavior of $L_n$ as $n$ gets large.

Information