The runsort permuton

Abstract

Suppose we choose a permutation $\ddot{I}€$ uniformly at random from $S_n$. Let $\mathsf{runsort}(\ddot{I}€)$ be the permutation obtained by sorting the ascending runs of $\ddot{I}€$ into lexicographic order. Alexandersson and Nabawanda recently asked if the plot of $\mathsf{runsort}(\ddot{I}€)$, when scaled to the unit square $[0,1{]}^2$, converges to a limit shape as $n\to \infty$. We answer their question by showing that the measures corresponding to the scaled plots of these permutations $\mathsf{runsort}(\ddot{I}€)$ converge with probability $1$ to a permuton (limiting probability distribution) that we describe explicitly. In particular, the support of this permuton is $\{(x,y)\in [0,1{]}^2:x\le y{e}^{1-y}\}$.