MONOTONE SUBSEQUENCES IN LOCALLY UNIFORM RANDOM PERMUTATIONS

• 成果类型: Article
• 署名作者: Sjostrand, Jonas
• 署名单位: Malardalen University
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/23-AOP1624
• 发表日期: 2023
• 页码: 1502-1547
• 关键词: longest increasing subsequence; length; shapes; LIMITS

摘要

A locally uniform random permutation is generated by sampling n points independently from some absolutely continuous distribution p 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, decreas-ing 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 & GE; 0, the largest union of ⠃r & RADIC;n ⠅ decreasing subsequences approaches a limit surface as n tends to infinity, and the limit surface is a solution to a specific varia-tional 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 p is the uniform dis-tribution 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.