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

Jérémie Bettinelli
École polytechnique
Laboratoire d'informatique (LIX)
91128 Palaiseau Cedex
FRANCE
Email: firstname « . » lastname « at » normalesup « . » org
Office: 2023
Phone: (+33) (0)1 77 57 80 61



Plane quadrangulations with a boundary 
back 

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 halfedges. 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.

Uniform plane quadrangulations with 10 000 faces and 200 halfedges (resp. 2 000 halfedges) 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.





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 halfedges 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 leftmost 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.