Growing uniform planar maps face by face

Alessandra Caraceni, Alexandre Stauffer

Research output: Contribution to journalArticlepeer-review

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 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 2faces, 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.

Original languageEnglish
Number of pages26
JournalRandom Structures and Algorithms
Early online date19 Jun 2023
DOIs
Publication statusE-pub ahead of print - 19 Jun 2023

Bibliographical note

Funding Information:
Supported by EPSRC Fellowship EP/N004566/1. Part of this work was done while the second author was also affiliated with the Department of Mathematics and Physics, Univ. Roma Tre, Rome, and the first author was supported by the Istituto Nazionale di Alta Matematica.

Keywords

  • random generation
  • random planar maps
  • random trees
  • triangulations

ASJC Scopus subject areas

  • Software
  • General Mathematics
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Growing uniform planar maps face by face'. Together they form a unique fingerprint.

Cite this