A Bijection for Tricellular Maps

We give a bijective proof for a relation between unicellular, bicellular, and tricellular maps. These maps represent cell complexes of orientable surfaces having one, two, or three boundary components. The relation can formally be obtained using matrix theory (Dyson, 1949) employing the Schwinger-Dyson equation (Schwinger, 1951). In this paper we present a bijective proof of the corresponding coefficient equation. Our result is a bijection that transforms a unicellular map of genus into unicellular, bicellular or tricellular maps of strictly lower genera. The bijection employs edge cutting, edge contraction, and edge deletion. 1. Introduction A -cellular map is a fatgraph having boundary components that are connected as a combinatorial graph. It can be interpreted as a cell complex whose geometric realization is a surface and as such encodes the invariants of the latter, as genus and orientability. A -cellular map is called unicellular and similarly -cellular and -cellular maps are referred to as bicellular and tricellular maps, respectively. Unicellular maps are also known as fatgraphs [1–3], having a unique boundary component. Unicellular maps were of central importance in a seminal paper of Harer and Zagier [4], who computed the virtual Euler characteristics of the Moduli space of curves. The virtual Euler characteristics were independently derived by Penner [5] by means of orthogonal polynomials. The key computation in [4] is that of the generating function of unicellular maps of genus having edges, . Their numbers, , satisfy the recursion: Another genus recursion, obtained by different means, namely, by splicing vertices, while keeping the number of edges constant, was derived in [6]. In the context of matrix theory [7, 8], the Schwinger-Dyson equation implies a relation of the generating functions of unicellular, , and bicellular maps, . This relation can also be obtained using representation theoretic framework [9] and is given by Recently, in [10] the authors presented a bijective proof of the corresponding coefficient equation of (2): which revealed a simple construction mechanism. The bijective proof can, for instance, be applied, to significantly speed up the folding of RNA interaction structures [11, 12]. This paper presents the bijective proof of the analogue of (3), relating to unicellular bicellular and tricellular maps. Formally, this relation be obtained via matrix theory and reads where is expressed in terms of the numbers of unicellular and bicellular maps. For the proof it is important to identify a suitable partition of the set of