A decorated tree approach to random permutations in substitution-closed classes
From MaRDI portal
(Redirected from Publication:782811)
Abstract: We establish a novel bijective encoding that represents permutations as forests of decorated (or enriched) trees. This allows us to prove local convergence of uniform random permutations from substitution-closed classes satisfying a criticality constraint. It also enables us to reprove and strengthen permuton limits for these classes in a new way, that uses a semi-local version of Aldous' skeleton decomposition for size-constrained Galton--Watson trees.
Recommendations
- Universal limits of substitution-closed permutation classes
- Local limit of the fixed point forest
- Scaling limits of permutation classes with a finite specification: a dichotomy
- Asymptotic normality of consecutive patterns in permutations encoded by generating trees with one‐dimensional labels
- Permutations with fixed pattern densities
Cites work
- scientific article; zbMATH DE number 1111349 (Why is no real title available?)
- scientific article; zbMATH DE number 3090543 (Why is no real title available?)
- An introduction to heavy-tailed and subexponential distributions
- Asymptotic fringe distributions for general families of random trees
- Average-case analysis of perfect sorting by reversals
- Condensation in nongeneric trees
- Critical multi-type Galton-Watson trees conditioned to be large
- Distances between pairs of vertices and vertical profile in conditioned Galton-Watson trees
- Excluded permutation matrices and the Stanley-Wilf conjecture
- Fixed points of 321-avoiding permutations
- Fringe trees, Crump-Mode-Jagers branching processes and \(m\)-ary search trees
- Functions of probability measures
- Gibbs partitions: The convergent case
- Growth rates of permutation grid classes, tours on graphs, and the spectral radius
- Invariance principles for Galton-Watson trees conditioned on the number of leaves
- Invariance principles for spatial multitype Galton-Watson trees
- Limit theorems for conditioned non-generic Galton-Watson trees
- Limits of permutation sequences
- Limits of random tree-like discrete structures
- 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
- Local limits of large Galton-Watson trees rerooted at a random vertex
- On scaling limits of multitype Galton-Watson trees with possibly infinite variance
- On the Brownian separable permuton
- On the maximal offspring in a subcritical branching process
- Pattern-avoiding permutations and Brownian excursion. I: Shapes and fluctuations.
- Pattern-avoiding permutations and Brownian excursion. II: Fixed points
- Patterns in random permutations avoiding some sets of multiple patterns
- Patterns in random permutations avoiding the pattern 321
- Random cutting and records in deterministic and random trees
- Random enriched trees with applications to random graphs
- Random measures, theory and applications
- Recurrence of distributional limits of finite planar graphs
- Scaling limit of multitype Galton-Watson trees with infinitely many types
- Scaling limits of Markov branching trees and Galton-Watson trees conditioned on the number of vertices with out-degree in a given set
- Schröder parenthesizations and chordates
- Schröder's problems and scaling limits of random trees
- Simple permutations and pattern restricted permutations
- Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
- The Brownian limit of separable permutations
- The continuum random tree. I
- The continuum random tree. III
- The expected shape of random doubly alternating Baxter permutations
- The infinite limit of random permutations avoiding patterns of length three
- The shape of random pattern-avoiding permutations
- Une nouvelle demonstration combinatoire des formules d'inversion de Lagrange
Cited in
(22)- The runsort permuton
- Bounded affine permutations. II: Avoidance of decreasing patterns
- 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
- Local convergence for permutations and local limits for uniform \(\rho \)-avoiding permutations with \(|\rho |=3\)
- Baxter permuton and Liouville quantum gravity
- The feasible region for consecutive patterns of permutations is a cycle polytope
- Exact-Size Sampling of Enriched Trees in Linear Time
- Square permutations are typically rectangular
- Mini-workshop: Permutation patterns. Abstracts from the mini-workshop held January 28 -- February 2, 2024
- Scaling limits of permutation classes with a finite specification: a dichotomy
- The skew Brownian permuton: A new universality class for random constrained permutations
- Substitution-closed pattern classes
- A Galton-Watson tree approach to local limits of permutations avoiding a pattern of length three
- The feasible region for consecutive patterns of permutations is a cycle polytope
- The number of occurrences of patterns in a random tree or forest permutation
- The feasible regions for consecutive patterns of pattern-avoiding permutations
- Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
- Asymptotic normality of consecutive patterns in permutations encoded by generating trees with one‐dimensional labels
- Almost square permutations are typically square
- Random cographs: Brownian graphon limit and asymptotic degree distribution
- Power-law bounds for increasing subsequences in Brownian separable permutons and homogeneous sets in Brownian cographons
This page was built for publication: A decorated tree approach to random permutations in substitution-closed classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q782811)
