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:
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:
