Séminaire Lotharingien de Combinatoire, 78B.79 (2017), 12 pp.

Gillaume Chapuy

On Tessellations of Random Maps and the tg-Recurrence

Abstract. The number of n-edge embedded graphs (rooted maps) on the g-torus grows as tgn5(g-1)/212n when n tends to infinity. The constants tg can be computed via the non-linear "tg-recurrence", strongly related to the KP hierarchy and the double scaling limit of the one-matrix model. The combinatorial meaning of this simple recurrence is still mysterious, and the purpose of this work is to point out an interpretation via random maps on surfaces. Namely, we show that the tg-recurrence is equivalent, via combinatorial bijections, to the fact that EXg2 = 1/3 for any g >= 0, where Xg,1-Xg are the masses of the nearest-neighbour cells surrounding two randomly chosen points in a Brownian map of genus g. This raises the question (that we leave open) of giving an independent probabilistic or combinatorial derivation of this second moment, which would lead to a fully concrete proof of the tg-recurrence. In fact, we conjecture that for any g >= 0 and k >= 2, the masses of the k nearest-neighbour cells induced by k uniform points in the genus g Brownian map form a uniform k-division of the unit interval. We leave this question open even for (g,k)=(0,2).

Received: November 14, 2016. Accepted: February 17, 2017. Final version: April 1, 2017.

The following versions are available: