2022/07/23 by Sjöstrand, Jonas
#60C05 (Primary) 05A05 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2207.11505
A locally uniform random permutation is generated by sampling n points independently from some absolutely continuous distribution ρ on the plane and interpreting them as a permutation by the rule that i maps to j if the ith point from the left is the jth point from below. As n tends to infinity, decreasing subsequences in the permutation will appear as curves in the plane, and by interpreting these as level curves, a union of decreasing subsequences give rise to a surface. We show that, under the correct scaling, for any r≥0, the largest union of \lfloor r√(n)\rfloor decreasing subsequences approaches a limit surface as n tends to infinity, and the limit surface is a solution to a specific variational problem. As a corollary, we prove the existence of a limit shape for the Young diagram associated to the random permutation under the Robinson-Schensted correspondence. In the special case where ρ is the uniform distribution on the diamond |x|+|y|<1 we conjecture that the limit shape is triangular, and assuming the conjecture is true we find an explicit formula for the limit surfaces of a uniformly random permutation and recover the famous limit shape of Vershik, Kerov and Logan, Shepp.