Universal limits of substitution-closed permutation classes
From MaRDI portal
Abstract: We consider uniform random permutations in proper substitution-closed classes and study their limiting behavior in the sense of permutons. The limit depends on the generating series of the simple permutations in the class. Under a mild sufficient condition, the limit is an elementary one-parameter deformation of the limit of uniform separable permutations, previously identified as the Brownian separable permuton. This limiting object is therefore in some sense universal. We identify two other regimes with different limiting objects. The first one is degenerate; the second one is nontrivial and related to stable trees. These results are obtained thanks to a characterization of the convergence of random permutons through the convergence of their expected pattern densities. The limit of expected pattern densities is then computed by using the substitution tree encoding of permutations and performing singularity analysis on the tree series.
This paper is about limiting objects of permutations whose building blocks are the so-called simple permutations: these are the permutations of the set \(\{1,\ldots, n\}\) that do not map an interval in another interval. The paper utilises a decomposition of a permutation into simple permutations under a certain set of rules. A key observation that facilitates the analysis is that this decomposition can be represented by a tree. The main result of this paper is about the limiting object of a random permutation that is sampled uniformly among all permutations that are generated by simple permutation of a given class. Under a certain condition on the generating function (and its radius of convergence) of this class, the authors show that the associated permuton of such a random permutation converges weakly (as a measure on \([0,1]^2\)) to the so-called biased Brownian permuton, which is introduced in the paper. It is characterised by specific frequencies of permutations of any fixed length \(\geq 2\). This notion is a generalisation of the unbiased Brownian permuton which was introduced by (a subset of) the authors in earlier work.
Recommendations
- LIMIT SETS OF RESTRICTED RANDOM SUBSTITUTIONS
- Universal cycles of k-subsets and k-permutations
- Scaling limits of permutation classes with a finite specification: a dichotomy
- scientific article; zbMATH DE number 1811347
- Universal cycles for permutation classes
- scientific article; zbMATH DE number 512831
- On the least exponential growth admitting uncountably many closed permutation classes
- scientific article; zbMATH DE number 4211145
- Limits of permutation sequences
Cites work
- A survey of simple permutations
- An algorithm for deciding the finiteness of the number of simple permutations in permutation classes
- Analytic combinatorics
- Area of Catalan paths on a checkerboard
- Boltzmann Samplers for the Random Generation of Combinatorial Structures
- Counting 1324, 4231-avoiding permutations
- Densities in large permutations and parameter testing
- Enumerating indices of Schubert varieties defined by inclusions
- Enumeration of pin-permutations
- Estimation in exponential families on permutations
- Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps
- Excluded permutation matrices and the Stanley-Wilf conjecture
- Expected patterns in permutation classes
- Finitely forcible graphons and permutons
- Fixed points and cycle structure of random permutations
- Generating and enumerating 321-avoiding and skew-merged simple permutations
- Geometry of permutation limits
- Growth rates of permutation grid classes, tours on graphs, and the spectral radius
- scientific article; zbMATH DE number 6683511 (Why is no real title available?)
- scientific article; zbMATH DE number 2186865 (Why is no real title available?)
- scientific article; zbMATH DE number 5831716 (Why is no real title available?)
- scientific article; zbMATH DE number 3900794 (Why is no real title available?)
- scientific article; zbMATH DE number 1354815 (Why is no real title available?)
- scientific article; zbMATH DE number 1859371 (Why is no real title available?)
- Inflations of geometric grid classes: three case studies
- Invariance principles for Galton-Watson trees conditioned on the number of leaves
- Large deviations and ratio limit theorems for pattern-avoiding permutations
- Limits of permutation sequences
- Longest monotone subsequences and rare regions of pattern-avoiding permutations
- On the asymptotic statistics of the number of occurrences of multiple permutation patterns
- On the Brownian separable permuton
- Pattern popularity in 132-avoiding permutations
- Pattern-avoiding permutations and Brownian excursion. I: Shapes and fluctuations.
- Pattern-avoiding permutations and Brownian excursion. II: Fixed points
- Patterns in random permutations avoiding the pattern 132
- Permutations with fixed pattern densities
- Random Trees
- Schröder's problems and scaling limits of random trees
- Simple permutations and pattern restricted permutations
- Simple permutations: Decidability and unavoidable substructures
- Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
- Some families of trees arising in permutation analysis
- Structure of random 312-avoiding permutations
- Substitution-closed pattern classes
- Surprising symmetries in objects counted by Catalan numbers
- The absence of a pattern and the occurrences of another
- The Brownian limit of separable permutations
- The continuum random tree. III
- The enumeration of permutations avoiding 2143 and 4231
- The enumeration of permutations avoiding 3124 and 4312
- The enumeration of three pattern classes using monotone grid classes
- The expected shape of random doubly alternating Baxter permutations
- The shape of random pattern-avoiding permutations
Cited in
(34)- Independence of permutation limits at infinitely many scales
- Almost square permutations are typically square
- The feasible regions for consecutive patterns of pattern-avoiding permutations
- The permuton limit of strong-Baxter and semi-Baxter permutations is the skew Brownian permuton
- Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes
- Scaling limits of permutation classes with a finite specification: a dichotomy
- Local convergence for permutations and local limits for uniform \(\rho \)-avoiding permutations with \(|\rho |=3\)
- Patterns in random permutations avoiding some sets of multiple patterns
- The runsort permuton
- LIMIT SETS OF RESTRICTED RANDOM SUBSTITUTIONS
- On the Brownian separable permuton
- Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
- The feasible region for consecutive patterns of permutations is a cycle polytope
- Exact-Size Sampling of Enriched Trees in Linear Time
- Random cographs: Brownian graphon limit and asymptotic degree distribution
- The skew Brownian permuton: A new universality class for random constrained permutations
- Baxter permuton and Liouville quantum gravity
- The number of occurrences of patterns in a random tree or forest permutation
- Substitution-closed pattern classes
- Power-law bounds for increasing subsequences in Brownian separable permutons and homogeneous sets in Brownian cographons
- Locally uniform random permutations with large increasing subsequences
- The permuton limit of random recursive separable permutations
- Mini-workshop: Permutation patterns. Abstracts from the mini-workshop held January 28 -- February 2, 2024
- Binary search trees of permuton samples
- Binary search trees of permuton samples
- Grothendieck shenanigans: permutons from pipe dreams via integrable probability
- Scaling limit of graph classes through split decomposition
- Subgraph densities and scaling limits of random graphs with a prescribed modular decomposition
- On the asymptotic enumeration and limit shapes of monotone grid classes of permutations
- On the sampling entropy of permutons
- Permutons, meanders, and SLE-decorated Liouville quantum gravity
- 3D permutations and triangle solitaire
- A decorated tree approach to random permutations in substitution-closed classes
- Bounded affine permutations. II: Avoidance of decreasing patterns
This page was built for publication: Universal limits of substitution-closed permutation classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2216743)
