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.
Mathematics Subject Classifications: 60C05, 05A05
Keywords: Random permutations, longest increasing subsequences, permutons