Where are the increasing subsequences?
Time: Wed 2016-12-14 10.15 - 11.15
Location: Room 3418, KTH math department
Participating: Jonas Sjöstrand
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!