Square permutations are tipically rectangular (with Erik Slivken)

ArXiv

A three-pages abstract for Permutation Patterns 2019

We can think of the records of a permutation (i.e., left-to-right or right-to-left maxima or minima) as the external points of a permutation. The points of a permutation that do not correspond to records are called internal points.  Square permutations are permutations with no internal points. Here an example and a counterexample:

The left permutation is a square permutation of size 8. The right permutation is not a square permutation since the red dot is an internal point.

We prove  that square permutations converge to a random permuton that can be described by a random rectangle embedded in \([0,1]^2 \) with edges of slope \(\pm 1\) .  The bottom corner of the rectangle is uniformly distributed. Here we can see two typical square permutations of size 1000:

We also show that the fluctuations about the lines of the rectangle of the permuton limit can be described by certain coupled Brownian motions. We considered the three colored families of points highlighted in the figure below (in blue, green and red) and we rotate them as shown in the picture. We then prove that the three rotated families  of points (on the right of the picture) converge to some coupled Brownian motions (after a suitable rescaling of distances).

We also look at square permutations from a local point of view. We consider the local topology for permutations introduced by the first author, that is the analogue of the celebrated Benjamini-Schramm convergence for graphs, and we look at the neighborhood of a random element of the permutation. We prove that uniform square permutations locally converge (in the quenched sense) to a random limiting object, described in terms of the following construction:

For each of the four cases, on the top line, we see the standard total order on the integer numbers with the integers labeled by "--" signs (painted in orange) and "+" signs (painted in blue). Then, in the bottom line of each of the four cases, we move the "--"-labeled numbers at the beginning of the new total order and the "+"-labeled numbers at the end. Moreover, for the first new total order we keep the relative order among integers with the same label, for the second one we reverse the order on the "--"-labeled numbers, for third one we reverse the order on the "+"-labeled numbers and for fourth one we reverse the order on both "--"-labeled and "+"-labeled numbers. For each case, reading the bottom line from left to right gives the new total order on integers.