Almost square permutations are typically square

Abstract

A record in a permutation is a maximum or a minimum, from the left or from the right. The entries of a permutation can be partitioned into two types: the ones that are records are called external points, the others are called internal points. Permutations without internal points have been studied under the name of square permutations. Here, we explore permutations with a fixed number of internals points, called almost square permutations. Unlike with square permutations, a precise enumeration for the total number of almost square permutations of size $n+k$ with exactly $k$ internal points is not known. However, using a probabilistic approach, we are able to determine the asymptotic enumeration. This allows us to describe the permuton limit of almost square permutations with $k$ internal points, both when $k$ is fixed and when $k$ tends to infinity along a negligible sequence with respect to the size of the permutation. Finally, we show that our techniques are quite general by studying the set of $321$-avoiding permutations of size $n$ with exactly $k$ additional internal points ($k$ fixed). In this case we obtain an interesting asymptotic enumeration in terms of the Brownian excursion area. As a consequence, we show that the points of a uniform permutation in this set concentrate on the diagonal and the fluctuations of these points converge in distribution to a biased Brownian excursion.

New version including referee's corrections, accepted for publication in Annales de l'Institut Henri Poincaré (B) Probabilités et Statistiques

References in corpus (10)

• Brownian excursion area, Wright's constants in graph enumeration, and other Brownian areas
• Universal limits of substitution-closed permutation classes
• 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$
• Square permutations are typically rectangular
• Grid polygons from permutations and their enumeration by the kernel method
• Fixed points of 321-avoiding permutations
• Bijections from Dyck paths to 321-avoiding permutations revisited
• A code for square permutations and convex permutominoes
• Almost avoiding permutations

Cited by in corpus (6)

• The feasible region for consecutive patterns of permutations is a cycle polytope
• Triangulations of simplices with vanishing local h-polynomial
• Splitting groups with cubic Cayley graphs of connectivity two
• Square permutations are typically rectangular
• Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes
• The skew Brownian permuton: a new universality class for random constrained permutations