LONG INCREASING SUBSEQUENCES IN UNIVERSAL BROWNIAN-TYPE PERMUTATIONS

ESB 2012

What is the behavior of the longest increasing subsequence of a uniformly random permutation? 

Its length is of order $2n^{1/2}$ plus Tracy--Widom fluctuations of order $n^{1/6}$. Its scaling limit is the directed geodesic of the directed landscape.

This talk discusses how this behavior changes dramatically when one looks at universal Brownian-type permutations, i.e., permutations sampled from the Brownian separable permutons. We show that there are explicit constants $1/2 < \alpha< \beta < 1$ such that the length of the longest increasing subsequence in a random permutation of size n sampled from the Brownian separable permutons is between $n^{\alpha - o(1)}$ and $n^{\beta + o(1)}$ with high probability. We present numerical simulations which suggest that the lower bound is close to optimal. 

Our proofs are based on the analysis of a fragmentation process embedded in a Brownian excursion introduced by Bertoin (2002).

If time permits, we conclude by discussing some conjectures for permutations sampled from the skew Brownian permutons, a model of universal permutons generalizing the Brownian separable permutons: here, the longest increasing subsequences should be closely related with some models of random directed metrics on planar maps.

Based on joint work with William Da Silva and Ewain Gwynne.