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

DOI10.1214/20-EJP469zbMATH Open1456.60030arXiv1904.07135MaRDI QIDQ782811FDOQ782811

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

Publication date: 29 July 2020

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

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.

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

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

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)

Cites Work

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

Cited In (22)

• 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
• A Galton-Watson tree approach to local limits of permutations avoiding a pattern of length three
• Substitution-closed pattern classes
• 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
• Linear-sized independent sets in random cographs and increasing subsequences in separable permutations
• The feasible regions for consecutive patterns of pattern-avoiding 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
• The runsort permuton

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)