Combinatorics Reading Seminar: Asymptotics of the longest increasing subsequence of a permutation

Seminar | September 25 | 11:10 a.m.-12:10 p.m. | 748 Evans Hall

 Jorge Garza Vargas, UC Berkeley

 Department of Mathematics

The main goal of this talk is to show that the longest increasing subsequence of a random permutation, when normalized by square root of n, converges in probability to the constant 2. We will begin the talk by briefly discussing previous results that address the simpler problem of finding the limit of the normalized expectation of the longest increasing subsequence. Then we will proceed to discuss the work of Aldous and Diaconis from 1995 in which connections are drawn between the longest increasing subsequence, Poisson point processes and an interacting particle process; in this work, Aldous and Diaconis showed that convergence in probability of the aforementioned quantity can be established as a byproduct of these connections.

 corteel@berkeley.edu