Universal limits of substitution-closed permutation classes

DOI10.4171/JEMS/993MaRDI QIDQ2216743zbMATH OpenOpenAlexFDO

Authors Frédérique Bassino, Mathilde Bouvel, Valentin Féray, L. Gerin, Mickaël Maazoun, Adeline Pierrot

Publication date 17 December 2020

Published in Journal of the European Mathematical Society (JEMS) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.08333

zbMATH Keywords

permutation patternssimple permutationspermutons

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05)

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.

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

• 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?)
• 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
• 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 Brownian separable permuton
• On the asymptotic statistics of the number of occurrences of multiple permutation patterns
• 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 Brownian limit of separable permutations
• The absence of a pattern and the occurrences of another
• 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

(26)

• The skew Brownian permuton: A new universality class for random constrained permutations
• On the Brownian separable permuton
• LIMIT SETS OF RESTRICTED RANDOM SUBSTITUTIONS
• Independence of permutation limits at infinitely many scales
• Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes
• Binary search trees of permuton samples
• Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
• Substitution-closed pattern classes
• A decorated tree approach to random permutations in substitution-closed classes
• Bounded affine permutations. II: Avoidance of decreasing patterns
• The permuton limit of random recursive separable permutations
• Locally uniform random permutations with large increasing subsequences
• Mini-workshop: Permutation patterns. Abstracts from the mini-workshop held January 28 -- February 2, 2024
• Almost square permutations are typically square
• Scaling limits of permutation classes with a finite specification: a dichotomy
• Exact-Size Sampling of Enriched Trees in Linear Time
• Baxter permuton and Liouville quantum gravity
• The runsort permuton
• Power-law bounds for increasing subsequences in Brownian separable permutons and homogeneous sets in Brownian cographons
• The feasible region for consecutive patterns of permutations is a cycle polytope
• The feasible regions for consecutive patterns of pattern-avoiding permutations
• Patterns in random permutations avoiding some sets of multiple patterns
• The permuton limit of strong-Baxter and semi-Baxter permutations is the skew Brownian permuton
• Random cographs: Brownian graphon limit and asymptotic degree distribution
• Local convergence for permutations and local limits for uniform \(\rho \)-avoiding permutations with \(|\rho |=3\)
• The number of occurrences of patterns in a random tree or forest permutation

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)