Bijections for planar maps with boundaries

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:158

Article

Bernardi, Olivier¹  Fusy, Eric² 

[1] Brandeis Univ, Dept Math, Waltham, MA 02254 USA

[2] Ecole Polytech, LIX, Palaiseau, France

关键词: Bijections;    Planar maps;    Boundaries;    Orientations;    Girth;    Dimers;   

DOI  :  10.1016/j.jcta.2018.03.001

来源: Elsevier

【 摘 要 】

We present bijections for planar maps with boundaries. In particular, we obtain bijections for triangulations and quadrangulations of the sphere with boundaries of prescribed lengths. For triangulations we recover the beautiful factorized formula obtained by Krikun using a (technically involved) generating function approach. The analogous formula for quadra.ngulations is new. We also obtain a far-reaching generalization for other face-degrees. In fact, all the known enumerative formulas for maps with boundaries are proved bijectively in the present article (and several new formulas are obtained). Our method is to show that maps with boundaries can be endowed with certain canonical orientations, making them amenable to the master bijection approach we developed in previous articles. As an application of our enumerative formulas, we note that they provide an exact solution of the dimer model on rooted triangulations and quadrangulations. (C) 2018 Elsevier Inc. All rights reserved.

【 授权许可】

Free