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

Growing uniform planar maps face by face

Caraceni, Alessandra
;
2023

Abstract

We provide “growth schemes” for inductively generating uniform random -angulations of the sphere with faces, as well as uniform random simple triangulations of the sphere with faces. In the case of -angulations, we provide a way to insert a new face at a random location in a uniform -angulation with faces in such a way that the new map is precisely a uniform -angulation with faces. Similarly, given a uniform simple triangulation of the sphere with faces, we describe a way to insert two new adjacent triangles so as to obtain a uniform simple triangulation of the sphere with faces. The latter is based on a new bijective presentation of simple triangulations that relies on a construction by Poulalhon and Schaeffer.
2023
Settore MAT/06 - Probabilita' e Statistica Matematica
random generation; random planar maps; random trees; triangulations
   Mathematical analysis of strongly correlated processes on discrete dynamic structures
   UK Research and Innovation
   EPSRC
   EP/N004566/1
File in questo prodotto:
File Dimensione Formato  
Random Struct Algorithms - 2023 - Caraceni - Growing uniform planar maps face by face-2.pdf

accesso aperto

Tipologia: Published version
Licenza: Creative Commons
Dimensione 1.74 MB
Formato Adobe PDF
1.74 MB Adobe PDF

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11384/131844
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
  • OpenAlex ND
social impact