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 -