The runsort permuton

2021/06/28 by Noga Alon, Colin Defant, Alon, Noga +3 · 3 citations
#05A05 #60F05 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2106.14762

Abstract

Suppose we choose a permutation π uniformly at random from S_n. 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]², 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]²:x≤ ye^1-y\.

Cited by

• Loose Hamiltonicity
• Convergence of sequences of ordered selections
• The p-θ relation in mating of trees

Related

• A geometric approach to conjugation-invariant random permutations
• Block size in Geometric(p)-biased permutations
• Permuton limits for some permutations avoiding a single pattern
• The permuton limit of random recursive separable permutations
• Some distributions in increasing and flattened permutations