论文标题
局部均匀随机排列中的单调子序
Monotone Subsequences in Locally Uniform Random Permutations
论文作者
论文摘要
本地统一的随机排列是通过独立于飞机上的某些连续分配$ρ$对$ n $点进行采样而产生的，并将其解释为规则，即如果左侧的$ j $ th点是$ j $ th的规则。由于$ n $倾向于无穷大，置换的子序列减少将以平面的曲线形式出现，并通过将其解释为水平曲线，降低子序列的结合会导致表面。我们表明，在正确的缩放下，对于任何$ r \ ge0 $，是$ \ lfloor r \ sqrt {n} \ rfloor $降低子序列的最大结合，因为$ n $倾向于无限，而极限表面是对特定变异问题的限制表面。作为推论，我们证明存在与罗宾逊 - 雪橇通讯下随机置换相关的年轻图的极限形状。在特殊情况下，$ρ$是钻石$ | x |+| y | <1 $上的均匀分布，我们认为极限形状是三角形的，并且假设猜想是正确的，我们找到了均匀随机置换的极限表面的明确公式，并恢复了Vershik，Kerov和Logan和Logan，Shepp，Shepp的著名限制形状。
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 $i$th point from the left is the $j$th 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\ge0$, the largest union of $\lfloor r\sqrt{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.
