A decorated tree approach to random permutations in substitution-closed classes

DOI10.1214/20-EJP469zbMath1456.60030arXiv1904.07135MaRDI QIDQ782811

Benedikt Stufler, Valentin Féray, Jacopo Borga, Mathilde Bouvel

Publication date: 29 July 2020

Published in: Electronic Journal of Probability (Search for Journal in Brave)

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

zbMATH Keywords

permutation patternsGalton-Watson treeslocal and scaling limits

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Related Items (18)

Bounded affine permutations. II: Avoidance of decreasing patterns ⋮ Linear-sized independent sets in random cographs and increasing subsequences in separable permutations ⋮ 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 ⋮ Square permutations are typically rectangular ⋮ The runsort permuton ⋮ Exact-Size Sampling of Enriched Trees in Linear Time ⋮ Asymptotic normality of consecutive patterns in permutations encoded by generating trees with one‐dimensional labels ⋮ 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 ⋮ Power-law bounds for increasing subsequences in Brownian separable permutons and homogeneous sets in Brownian cographons ⋮ Local convergence for permutations and local limits for uniform \(\rho \)-avoiding permutations with \(|\rho |=3\) ⋮ The feasible region for consecutive patterns of permutations is a cycle polytope ⋮ The feasible region for consecutive patterns of permutations is a cycle polytope ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• The shape of random pattern-avoiding permutations
• Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
• Invariance principles for Galton-Watson trees conditioned on the number of leaves
• Scaling limit of multitype Galton-Watson trees with infinitely many types
• Fringe trees, Crump-Mode-Jagers branching processes and \(m\)-ary search trees
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Condensation in nongeneric trees
• Pattern-avoiding permutations and Brownian excursion. II: Fixed points
• Invariance principles for spatial multitype Galton-Watson trees
• The continuum random tree. I
• Asymptotic fringe distributions for general families of random trees
• Une nouvelle demonstration combinatoire des formules d'inversion de Lagrange
• Schröder parenthesizations and chordates
• Functions of probability measures
• Random enriched trees with applications to random graphs
• The Brownian limit of separable permutations
• Critical multi-type Galton-Watson trees conditioned to be large
• Local limits of large Galton-Watson trees rerooted at a random vertex
• Local convergence of large critical multi-type Galton-Watson trees and applications to random maps
• Recurrence of distributional limits of finite planar graphs
• Limits of permutation sequences
• Limits of random tree-like discrete structures
• On the maximal offspring in a subcritical branching process
• 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
• Limit theorems for conditioned non-generic Galton-Watson trees
• Scaling limits of Markov branching trees and Galton-Watson trees conditioned on the number of vertices with out-degree in a given set
• The continuum random tree. III
• Simple permutations and pattern restricted permutations
• AVERAGE-CASE ANALYSIS OF PERFECT SORTING BY REVERSALS
• Schröder’s problems and scaling limits of random trees
• Random Measures, Theory and Applications
• Random cutting and records in deterministic and random trees
• On scaling limits of multitype Galton-Watson trees with possibly infinite variance
• Fixed points of 321-avoiding permutations
• An Introduction to Heavy-Tailed and Subexponential Distributions
• Gibbs partitions: The convergent case
• On the Brownian separable permuton
• Distances between pairs of vertices and vertical profile in conditioned Galton–Watson trees
• The Infinite limit of random permutations avoiding patterns of length three
• Patterns in random permutations avoiding the pattern 321
• Growth rates of permutation grid classes, tours on graphs, and the spectral radius
• The Expected Shape of Random Doubly Alternating Baxter Permutations
• Pattern‐avoiding permutations and Brownian excursion part I: Shapes and fluctuations

This page was built for publication: A decorated tree approach to random permutations in substitution-closed classes