Locally uniform random permutations with large increasing subsequences

Abstract

We investigate the maximal size of an increasing subset among points randomly sampled from certain probability densities. Kerov and Vershik's celebrated result states that the largest increasing subset among $N$ uniformly random points on $[0,1{]}^2$ has size asymptotically $2\sqrt{N}$. More generally, the order $\Theta (\sqrt{N})$ still holds if the sampling density is continuous. In this paper we exhibit two sufficient conditions on the density to obtain a growth rate equivalent to any given power of $N$ greater than $\sqrt{N}$, up to logarithmic factors. Our proofs use methods of slicing the unit square into appropriate grids, and investigating sampled points appearing in each box.

18 pages, 4 figures

References in corpus (4)

• Universal limits of substitution-closed permutation classes
• Fixed points and cycle structure of random permutations
• Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
• Increasing subsequences of linear size in random permutations and the Robinson-Schensted tableaux of permutons

Cited by in corpus (2)

• Increasing subsequences of linear size in random permutations and the Robinson-Schensted tableaux of permutons
• Binary search trees of permuton samples