Increasing subsequences in locally uniform random permutations

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 non-uniform distributions, and even a kind of continuous R-S correspondence.