Apr. 07, 2008
Fraydoun Rezakhanlou
Random Growth Models, Combinatorics and the Hamilton-Jacobi Equation
As a classical problem in combinatorics, consider the longest increasing
subsequence of a random permutation of the sequence 1,2,...,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 are of order n^{1/6}. In this lecture, 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 the Hammersely
model is used to get insight into the behavior of L_n as n gets large.
This model is one of the most basic examples of growth processes which are
described by Hamilton-Jacobi PDEs in macroscopic coordinates.
PDF