Growing uniform planar maps face by face

DOI10.1002/RSA.21165MaRDI QIDQ6063346zbMATH OpenOpenAlexFDO

Authors Alessandra Caraceni, Alexandre Stauffer

Publication date 7 November 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

random generationrandom planar mapsrandom treestriangulations

Mathematics Subject Classification ID

Combinatorics (05-XX) Numerical analysis (65-XX)

Abstract: We provide "growth schemes" for inductively generating uniform random $2p$-angulations of the sphere with $n$ faces, as well as uniform random simple triangulations of the sphere with $2n$ faces. In the case of $2p$-angulations, we provide a way to insert a new face at a random location in a uniform $2p$-angulation with $n$ faces in such a way that the new map is precisely a uniform $2p$-angulation with $n+1$ faces. Similarly, given a uniform simple triangulation of the sphere with $2n$ faces, we describe a way to insert two new adjacent triangles so as to obtain a uniform simple triangulation of the sphere with $2n+2$ faces. The latter is based on a new bijective presentation of simple triangulations that relies on a construction by Poulalhon and Schaeffer.

Recommendations

• Planar stochastic hyperbolic triangulations
• A bijection for triangulations, quadrangulations, pentagulations, etc.
• Growing random 3-connected maps or \textit{Comment s'enfuir de l'hexagone}
• Uniform infinite planar triangulations
• Random sampling of large planar maps and convex polyhedra

Cites work

• A bijection for triangulations, quadrangulations, pentagulations, etc.
• A Census of Planar Maps
• A Census of Planar Triangulations
• A generic method for bijections between blossoming trees and planar maps
• A linear-time algorithm for the generation of trees
• A polynomial upper bound for the mixing time of edge rotations on planar maps
• Building uniformly random subtrees
• Growing random 3-connected maps or \textit{Comment s'enfuir de l'hexagone}
• scientific article; zbMATH DE number 3900794 (Why is no real title available?)
• Increasing forests and quadrangulations via a bijective approach
• Optimal coding and sampling of triangulations
• Planar Maps are Well Labeled Trees
• Planar maps as labeled mobiles
• Polynomial mixing time of edge flips on quadrangulations
• Scaling limits of multi-type Markov branching trees
• Scaling limits of random trees and planar maps
• Unified bijections for maps with prescribed degrees and girth
• Uniform infinite planar triangulations

Cited in

(1)

• Where do (random) trees grow leaves?

This page was built for publication: Growing uniform planar maps face by face

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6063346)