The longest increasing subsequence of Brownian separable permutons
Vienna Probability Seminar
The Brownian separable permutons form a one-parameter family of permutons, which are the universal scaling limits of pattern-avoiding permutations. In this talk, we will be interested in the length of the longest increasing subsequence (LIS) in permutations of size n sampled from the Brownian permutons. We give an answer to the celebrated Ulam-Hammersley problem in this context: what is the exact behaviour of LIS as n goes to infinity? In fact, we prove a more precise scaling limit result for the LIS. A significant portion of the talk will be dedicated to our motivation behind the problem, emphasising connections to various objects in probability, such as random decorated trees, random graphs, directed planar maps and SLE/LQG. The talk is based on joint work with Arka Adhikari, Jacopo Borga, Thomas Budzinski and Delphin Snizergues.