Jacopo Borga (Standord University)
Monday, April 3, 2023 - 2:30pm to 3:30pm
ECE 026
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.