Increasing subsequences in locally uniform random permutations

Background

It has been known since the 1970s that the length of the longest increasing subsequence in a random permutation of order n is twice the square root of n for large n. More generally, the (scaled) limit of the cardinality of the largest union of r times the square root of n disjoint increasing subsequences is known for any positive r. But what does this union typically look like in the permutation diagram? And what if the permutation is not sampled uniformly? The aim of this project is to answer these questions, at least for a family of distributions called locally uniform. A locally uniform random permutation is obtained by sampling n points independently in the unit square from some given distribution and then interpret these points as a permutation mapping i to j if the i-th point from the left is the j-th point from below. In this setting, when n is large, increasing subsequences appear as curves, and we can think of these as level curves of a 2D surface. As n tends to infinity, we might hope to obtain a limit surface for a maximal union of k increasing subsequences, where k depends on n. This approach is novel even for uniform random permutations and could possibly lead to a new proof of the famous result by Vershik-Kerov and Logan-Shepp on the limit shape of the Young diagram corresponding to a random permutation under Robinson-Schensted. It might also produce corresponding limit-shape results for nonuniform distributions, and even a kind of continuous R-S correspondence.

Purpose

The purpose is to improve our understanding of the structure of increasing subsequences in random permutations. This is a natural first step towards the greater goal of creating a theory of random permutations analogous to the rich existing theory of random graphs.

Activities

The plan is to first consider random permutations generated by a Poisson point process on the diamond region |x| + |y| < 1 and probably use some kind of subergodic theorem to establish the existence of limiting sizes of unions of increasing subsequences in those. Then, by gluing together multiple rescaled and translated versions of the diamond, we hope to be able to handle random permutations generated by an inhomogeneous Poisson point sequence on a general region.

Project objective

The objective is to answer the following questions:

1. For large n and constant r, where in the permutation diagram does a maximal union of r sqrt(n) increasing subsequences typically reside?
   
2. What happens if the permutation is not uniformly but only locally uniformly random?