Random Permutations -- A geometric point of view

Abstract

We look at geometric limits of large random non-uniform permutations. We mainly consider two theories for limits of permutations: permuton limits, introduced by Hoppen, Kohayakawa, Moreira, Rath, and Sampaio to define a notion of scaling limits for permutations; and Benjamini-Schramm limits, introduced by the author to define a notion of local limits for permutations. The models of random permutations that we consider are mainly constrained models, that is, uniform permutations belonging to a given subset of the set of all permutations. We often identify this subset using pattern-avoidance, focusing on: permutations avoiding a pattern of length three, substitution-closed classes, (almost) square permutations, permutation families encoded by generating trees, and Baxter permutations. We explore some universal phenomena for the models mentioned above. For Benjamini-Schramm limits we explore a concentration phenomenon for the limiting objects. For permuton limits we deepen the study of some known universal permutons, called biased Brownian separable permutons, and we introduce some new ones, called Baxter permuton and skew Brownian permutons. In addition, for (almost) square permutations, we investigate the occurrence of a phase transition for the limiting permutons. On the way, we establish various combinatorial results both for permutations and other related objects. Among others, we give a complete description of the feasible region for consecutive patterns as the cycle polytope of a specific graph; and we find new bijections relating Baxter permutations, bipolar orientations, walks in cones, and a new family of discrete objects called coalescent-walk processes.

arXiv commentThis is a Ph.D. thesis. Most of the material in this manusript is taken from previous articles written by the author. Nevertheless, we highlight that, in order to give a more pleasant and organic presentation of the various results obtained by the author during his Ph.D., we opt for a completely different organization of the material compared to the exposition in the various papers

References in corpus (19)

• Uniqueness and universality of the Brownian map
• Graph limits and exchangeable random graphs
• Flows, coalescence and noise
• Random walks in cones
• Local structure of random quadrangulations
• Invariance principles for Galton-Watson trees conditioned on the number of leaves
• Mating of trees for random planar maps and Liouville quantum gravity: a survey
• Patterns in random permutations avoiding the pattern 132
• Universal limits of substitution-closed permutation classes
• The Archimedean limit of random sorting networks
• Fixed points and cycle structure of random permutations
• On the Height Profile of a Conditioned Galton-Watson Tree
• Grid polygons from permutations and their enumeration by the kernel method
• A central limit theorem for descents of a Mallows permutation and its inverse
• Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes
• Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
• The Expected Shape of Random Doubly Alternating Baxter Permutations
• Scaling limits of permutations avoiding long decreasing sequences
• Quenched law of large numbers and quenched central limit theorem for multi-player leagues with ergodic strengths

Cited by in corpus (2)

• 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