Where are the increasing subsequences?

Abstract

It has been known since the 1970s that the longest increasing subsequence of a random permutation of {1,2,...,n} has length approximately twice the square root of n for large n. More generally, the (scaled) limit of the size of the largest union of r sqrt(n) disjoint increasing subsequences is known for any r. But what does this union typically look like in the permutation diagram? And what if the permutation is not sampled from the uniform distribution? In this talk I will discuss these directions of research and present a new intriguing conjecture!