Scaling limits of permutation classes with a finite specification: a dichotomy
This paper provides the limiting distribution of a random permutation on \(n\) elements (without loss of generality, on the set \(\{1,\ldots, n\}\)) sampled uniformly from a class of permutations which admit combinatorial specification. Roughly speaking, such a permutation can be written recursively in terms of substitutions with permutations from the same class, but with certain specifications (one of which is that the substituting permutation may be among the simple permutations in the class). In fact, the paper considers families of such classes allowing substitution from each one of them. This gives rise to a system of generating functions which describes the dependencies between the generating functions of these classes. An important notion that is associated with these generating functions is that of criticality. The sub-family of generating functions whose radius of convergence is minimum is are called critical (this term is also applied to the family itself whose generating function is critical). Now, system which describes the dependencies between these functions gives rise to a directed graph on these families of permutation, where an arrow is added from one family to another if the generating function of the latter depends on the generating function of the former. The paper assumes that the subgraph induced by the critical families is strongly connected. The two main results of the paper identify a dichotomy on the limiting object of such random permutations. One sub-class of them (that satisfies certain properties) converge in distribution to a (deterministic) X-shaped permuton. The other sub-class converge to the same so-called Brownian permuton. (In this context, the term ``convergence refers to the convergence of the associated measure on \([0,1]^2\) that is induced by a permutation.)
- A calculus for the random generation of labelled combinatorial structures
- A decorated tree approach to random permutations in substitution-closed classes
- An algorithm computing combinatorial specifications of permutation classes
- Analytic combinatorics
- Boltzmann Samplers for the Random Generation of Combinatorial Structures
- Combinatorics of permutations
- Decomposing simple permutations, with enumerative consequences
- Enumeration of pin-permutations
- Finitely forcible graphons and permutons
- Formulae and asymptotics for coefficients of algebraic functions
- scientific article; zbMATH DE number 2186865 (Why is no real title available?)
- scientific article; zbMATH DE number 986989 (Why is no real title available?)
- scientific article; zbMATH DE number 3274494 (Why is no real title available?)
- Invariance principles for spatial multitype Galton-Watson trees
- Limit theorems for triangular urn schemes
- Limits of permutation sequences
- Local convergence for permutations and local limits for uniform \(\rho \)-avoiding permutations with \(|\rho |=3\)
- Local convergence of large critical multi-type Galton-Watson trees and applications to random maps
- On the Brownian separable permuton
- Packing rates of measures and a conjecture for the packing density of 2413
- Pattern-avoiding permutations and Brownian excursion. I: Shapes and fluctuations.
- Patterns in random permutations avoiding the pattern 132
- Patterns in random permutations avoiding the pattern 321
- Permutation classes
- Random Trees
- Simple permutations and algebraic generating functions
- Simple permutations and pattern restricted permutations
- Simple permutations: Decidability and unavoidable substructures
- Structure of random 312-avoiding permutations
- The Brownian limit of separable permutations
- The shape of random pattern-avoiding permutations
- The X-class and almost-increasing permutations
- Universal limits of substitution-closed permutation classes
- Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes
- Universal limits of substitution-closed permutation classes
- Limit densities of patterns in permutation inflations
- The runsort permuton
- On the Brownian separable permuton
- Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
- Permutations with fixed pattern densities
- scientific article; zbMATH DE number 7651046 (Why is no real title available?)
- The skew Brownian permuton: A new universality class for random constrained permutations
- Continuity of limit surfaces of locally uniform random permutations
- Baxter permuton and Liouville quantum gravity
- Power-law bounds for increasing subsequences in Brownian separable permutons and homogeneous sets in Brownian cographons
- Locally uniform random permutations with large increasing subsequences
- Scaling limits of permutation classes with a finite specification: a dichotomy
- The permuton limit of random recursive separable permutations
- A logical limit law for \(231\)-avoiding permutations
- Mini-workshop: Permutation patterns. Abstracts from the mini-workshop held January 28 -- February 2, 2024
- Increasing subsequences of linear size in random permutations and the Robinson-Schensted tableaux of permutons
- Scaling limit of graph classes through split decomposition
- On the asymptotic enumeration and limit shapes of monotone grid classes of permutations
- On the sampling entropy of permutons
- A decorated tree approach to random permutations in substitution-closed classes
This page was built for publication: Scaling limits of permutation classes with a finite specification: a dichotomy
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2155196)
