TY - JOUR

T1 - The runsort permuton

AU - Alon, Noga

AU - Defant, Colin

AU - Kravitz, Noah

N1 - Funding Information:
The first author is supported in part by NSF grant DMS–1855464 , BSF grant 2018267 , and the Simons Foundation . The second author is supported by an NSF Graduate Research Fellowship (grant DGE–1656466 ) and a Fannie and John Hertz Foundation Fellowship. The third author is supported by an NSF Graduate Research Fellowship (grant DGE–2039656 ). We are grateful to Ryan Alweiss, Peter Winkler, and Zach Hunter for helpful conversations. We also thank the anonymous referee for helpful comments.
Publisher Copyright:
© 2022 Elsevier Inc.

PY - 2022/8

Y1 - 2022/8

N2 - Suppose we choose a permutation π uniformly at random from Sn. Let runsort(π) be the permutation obtained by sorting the ascending runs of π into lexicographic order. Alexandersson and Nabawanda recently asked if the plot of runsort(π), when scaled to the unit square [0,1]2, converges to a limit shape as n→∞. We answer their question by showing that the measures corresponding to the scaled plots of these permutations runsort(π) converge with probability 1 to a permuton (limiting probability distribution) that we describe explicitly. In particular, the support of this permuton is {(x,y)∈[0,1]2:x≤ye1−y}.

AB - Suppose we choose a permutation π uniformly at random from Sn. Let runsort(π) be the permutation obtained by sorting the ascending runs of π into lexicographic order. Alexandersson and Nabawanda recently asked if the plot of runsort(π), when scaled to the unit square [0,1]2, converges to a limit shape as n→∞. We answer their question by showing that the measures corresponding to the scaled plots of these permutations runsort(π) converge with probability 1 to a permuton (limiting probability distribution) that we describe explicitly. In particular, the support of this permuton is {(x,y)∈[0,1]2:x≤ye1−y}.

UR - http://www.scopus.com/inward/record.url?scp=85129727724&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85129727724&partnerID=8YFLogxK

U2 - 10.1016/j.aam.2022.102361

DO - 10.1016/j.aam.2022.102361

M3 - Article

AN - SCOPUS:85129727724

SN - 0196-8858

VL - 139

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

M1 - 102361

ER -