Unified bijections for maps with prescribed degrees and girth

Abstract: This article presents unified bijective constructions for planar maps, with control on the face degrees and on the girth. Recall that the girth is the length of the smallest cycle, so that maps of girth at least

d = 1, 2, 3

are respectively the general, loopless, and simple maps. For each positive integer

d

, we obtain a bijection for the class of plane maps (maps with one distinguished root-face) of girth

d

having a root-face of degree

d

. We then obtain more general bijective constructions for annular maps (maps with two distinguished root-faces) of girth at least

d

. Our bijections associate to each map a decorated plane tree, and non-root faces of degree

k

of the map correspond to vertices of degree

k

of the tree. As special cases we recover several known bijections for bipartite maps, loopless triangulations, simple triangulations, simple quadrangulations, etc. Our work unifies and greatly extends these bijective constructions. In terms of counting, we obtain for each integer

d

an expression for the generating function

F_{d} (x_{d}, x_{d + 1}, x_{d + 2}, ...)

of plane maps of girth

d

with root-face of degree

d

, where the variable

x_{k}

counts the non-root faces of degree

k

. The expression for

F_{1}

was already obtained bijectively by Bouttier, Di Francesco and Guitter, but for

d g e q 2

the expression of

F_{d}

is new. We also obtain an expression for the generating function

G_{p, q}^{(d, e)} (x_{d}, x_{d + 1}, ...)

of annular maps with root-faces of degrees

p

and

q

, such that cycles separating the two root-faces have length at least

e

while other cycles have length at least

d

. Our strategy is to obtain all the bijections as specializations of a single "master bijection" introduced by the authors in a previous article. In order to use this approach, we exhibit certain "canonical orientations" characterizing maps with prescribed girth constraints.

Recommendations

Cites work

Cited in

(24)

This page was built for publication: Unified bijections for maps with prescribed degrees and girth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q423656)