Square permutations are typically rectangular

Abstract

We describe the limit (for two topologies) of large uniform random square permutations, i.e., permutations where every point is a record. The starting point for all our results is a sampling procedure for asymptotically uniform square permutations. Building on that, we first describe the global behavior by showing that these permutations have a permuton limit which can be described by a random rectangle. We also explore fluctuations about this random rectangle, which we can describe through coupled Brownian motions. Second, we consider the limiting behavior of the neighborhood of a point in the permutation through local limits. As a byproduct, we also determine the random limits of the proportion of occurrences (and consecutive occurrences) of any given pattern in a uniform random square permutation.

arXiv commentNew version including referee's corrections, accepted for publication in Annals of Applied Probability

References in corpus (12)

• Thermodynamic Limit for the Mallows Model on $S_n$
• Patterns in random permutations avoiding the pattern 132
• A decorated tree approach to random permutations in substitution-closed classes
• Local convergence for permutations and local limits for uniform $\rho$-avoiding permutations with $|\rho |=3$
• On the Brownian separable permuton
• Grid polygons from permutations and their enumeration by the kernel method
• Fixed points of 321-avoiding permutations
• Almost square permutations are typically square
• Growth rates of permutation grid classes, tours on graphs, and the spectral radius
• Permutations avoiding 312 and another pattern, Chebyshev polynomials and longest increasing subsequences
• A code for square permutations and convex permutominoes
• Asymptotic distribution of fixed points of pattern-avoiding involutions

Cited by in corpus (8)

• Local convergence for permutations and local limits for uniform $\rho$-avoiding permutations with $|\rho |=3$
• Almost square permutations are typically square
• Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes
• Asymptotic normality of consecutive patterns in permutations encoded by generating trees with one-dimensional labels
• The skew Brownian permuton: a new universality class for random constrained permutations
• Increasing subsequences of linear size in random permutations and the Robinson-Schensted tableaux of permutons
• Bounded affine permutations II. Avoidance of decreasing patterns
• On the asymptotic enumeration and limit shapes of monotone grid classes of permutations