UBC Probability Seminar: Jacopo Borga

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

Its length is of order 2n1/2 plus Tracy--Widom fluctuations of order n1/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<α<β<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α−o(1) and nβ+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.