version française
Désolé, pas de version française pour cette page...

Jérémie Bettinelli

École polytechnique
Laboratoire d'informatique (LIX)
91128 Palaiseau Cedex
E-mail: firstname « . » lastname « at » normalesup « . » org
Office: 2023
Phone: (+33) (0)1 77 57 80 61

Plane quadrangulations with a boundary


Sketchfab folderPicture folder

We now look at quadrangulations of more general surfaces. The first natural generalization is to consider the case of the disk. More precisely, a plane quadrangulation with a boundary is a plane map of the sphere where all the faces except one (the external face) are incident to 4 half-edges. The external face should be thought of as a hole in the sphere and it is not represented on the figures (only its boundary is visible). Note also that this boundary is not necessary (and actually very unlikely to be) a simple curve, so that, although the surface is very close to a disk, it is not exactly one. However, the main result of Scaling Limit of Random Planar Quadrangulations with a Boundary states that, in the limit for the right scaling, when the length of the boundary is of order the square root of the number of faces, the object that arises is a topological disk. In contrast, when the length of the boundary grows faster than the square root of the number of faces, we obtain a Brownian tree in the limit, that is, the same object as for a uniform tree. This can be intuited from the following simulations.

Disk 10k_100 [jpg1jpg2pdf1pdf23D pdfu3d&tex]   Disk 10k_1k [jpg1jpg2pdf1pdf23D pdfu3d&tex]

Uniform plane quadrangulations with 10 000 faces and 200 half-edges (resp. 2 000 half-edges) on the boundary

Cactus embedding

Here, we may also look at the cactus embedding of these plane quadrangulations with a boundary. The boundary is outlined in red.

Brownian map Brownian map
n = 10 000 and p = 100 n = 10 000 and p = 1 000
Cactus embedding of a uniform plane quadrangulation with n faces and 2p half-edges on the boundary

Slice decomposition

The slice decomposition follows from an idea of Bouttier and Guitter. We still consider plane quadrangulations with a boundary and we represent the slices by different (random) colors. The slices are defined as follows. First, pick a vertex uniformly at random in the map. Then, for every vertex on the boundary, consider the left-most geodesic in the map starting from this vertex and ending at the vertex you picked. The slices are the pieces of the map that are delimited by these geodesics.

Sliced disk 10k_1k [jpggifpdf]   Sliced disk 10k_100 [jpggif1gif2gif3pdf]   Sliced disk 30k_150 [jpgpdf]   Sliced disk 40k_500 [jpgpdf]


Valid XHTML 1.0 Strict