2021/10/27 by Caraceni, Alessandra, Stauffer, Alexandre
#05C30 #60C05 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2110.14575
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.