On the growth of random planar maps with a prescribed degree sequence

Abstract

For non-negative integers $(d_n(k){)}_{k\ge 1}$ such that ${\sum }_{k\ge 1}{d}_n(k)=n$, we sample a bipartite planar map with $n$ faces uniformly at random amongst those which have $d_n(k)$ faces of degree $2k$ for every $k\ge 1$ and we study its asymptotic behaviour as $n\to \infty$. We prove that the diameter of such maps grow like ${\sigma }_n^{1/2}$, where ${\sigma }_n^2={\sum }_{k\ge 1}k(k-1)d_n(k)$ is a global variance term. More precisely, we prove that the vertex-set of these maps equipped with the graph distance divided by ${\sigma }_n^{1/2}$ and the uniform probability measure always admits subsequential limits in the Gromov-Hausdorff-Prokhorov topology. Our proof relies on a bijection with random labelled trees; we are able to prove that the label process is always tight when suitably rescaled, even if the underlying tree is not tight for the Gromov-Hausdorff topology. We also rely on a new spinal decomposition which is of independent interest. Finally this paper also serves as a toolbox for a companion paper in which we discuss more precisely Brownian limits of such maps.

Obsolete paper which has now been merged with the companion paper available at arXiv:1903.06138