# A Bijection for Tricellular Maps

Authors: Hillary S. W. Han; Christian M. Reidys
Journal: ISRN Discrete Mathematics
 (2013)

---

## Abstract

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 genusg into unicellular, bicellular or tricellular maps of strictly lower genera. The bijection employs edge cutting, edge contraction, and edge deletion.


---

## Body

## 1. Introduction

Ak-cellular map is a fatgraph having k 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.A1-cellular map is called unicellular and similarly 2-cellular and 3-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 g having n edges, Ug(z). Their numbers, ug(n), satisfy the recursion:
(1)(n+1)ug(n)=2(2n-1)ug(n-1)+(2n-1)(n-1)(2n-3)ug-1(n-2).
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, Ug(z), and bicellular maps, Bg(z). This relation can also be obtained using representation theoretic framework [9] and is given by
(2)∑g1=0g+1Ug1(z)Ug+1-g1(z)+Bg(z)=Ug+1(z)z.
Recently, in [10] the authors presented a bijective proof of the corresponding coefficient equation of (2):
(3)∑g1=0g+1∑i≥0nug1(i)ug+1-g1(n-i)+bg(n)=ug+1(n+1),
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
(4)ug+2(n+2)=tg(n)+dg+2(n)+4ug+2(n+1)-3ug+2(n)+(n+1)(2n+1)ug+1(n),
where dg+2(n) 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 unicellular maps of genus (g+2) with (n+2) edges.It is worth mentioning that matrix theory does not provide insight into a recursion involving quadricellular maps. In fact it seems unlikely that such a relation can be derived using the formal framework. The bijective proof presented here is however rather intuitive, once the correct partitioning is identified. We believe that it is possible to prove similar relations for maps with more than three boundary components.


## 2. Basic Definitions

LetS2n denote the permutation group over 2n elements.Definition 1.
Letk,J be positive integers. A k-cellular map is a triple (H,α,(γi)1≤i≤k), where H is a set of cardinality 2n, α is a fixed-point free involution and γi are cycles such that γ=∏i=1k‍γi∈S2n. The elements of H are called half-edges, and the cycles of α are called edges. The cycles of the permutation σ=α∘γ are the vertices vi, 1≤i≤J. The length of vi is its degree. The cycle γi is called the ith face.The associated combinatorial graphG of a k-cellular map is the graph whose edges and vertices are the cycles of α and σ. We can regard a G-edge as a ribbon whose two sides are labeled by the half-edges as follows: each side of the ribbon represents one half-edge, we decide which half-edge corresponds to which side of the ribbon by the convention that, if a half-edge h belongs to a cycle e of α and a certain v of σ, and then h is the right-hand side of the ribbon corresponding to e, when entering v.We draw the graphG in such a way that, around each vertex v, the counterclockwise ordering of the half-edges belonging to the cycle v is given by that cycle. This ordering of half-edges enriches the combinatorial graph G to a ribbon graph or fat graph 𝔾. Clearly, a fat graph 𝔾 with its boundary components is tantamount to the k-cellular map (H,α,(γi)i). (γi)i is interpreted as the cycle of half-edges visited when making the tour of the graph, keeping the graph on its left.For the orbits of[1,2n]∈S2n under the action of the subgroup of S2n generated by α, σ, and γ are called the connected components of the k-cellular map. If this action is transitive, we say that the associated graph G and fat graph 𝔾 of the k-cellular map are connected. Topologically, G is a deformation retract of the surface with boundary 𝔾.Definition 2.
A plantedk-cellular map is a k-cellular map in which each γi contains a distinguished half-edge pi, such that (pi) is a σ-cycle. (pi) is called the plant of the face γi and σ-cycles, except that the plants are called (np) vertices.In the following, we refer to edges not incident to plants as(np) edges. Let Xk(n) denote the set of planted k-cellular maps that contain n(np) edges.In planted maps we will label the half-edges ofH such that (α(pi),pi)=(Ri,Si), that is,
(5)γ1=(R1,1,2,…,m1,S1),γi=(Ri,mi-1+1,mi-1+2,…,mi-1,mi,Si),hhhhhhhhhhhhhhhhhhhhhhhhhh2≤i≤k.
Given xk,n∈Xk(n) we define the linear order <γ on H for each face γi via
(6)Si-1<γRi<γγi(Ri)<γγi2(Ri)<γ⋯<γγimi(Ri)<γγimi+1(Ri)=Si.
Let furthermore Hγ1,…,γr denote the set consisting of the half-edges in one of these faces γi, 1≤i≤k. In particular, Hγi is the set of half-edges contained in the face γi.There is a natural equivalence relation over half-edges,h~α(h) and in particular, α(pi)~pi. If h,α(h)∈Hγi, then (h,α(h)) is called a one-sided edge and (h,α(h)) is called a two-sided edge, otherwise.For each vertexvj, let minx(vj) denote the first half-edge via which γi enters vj. This gives a canonical way of writing the cycle, starting at hj1=min(vj), namely, vj=(hj1,…,hjnj). In particular, the vertex containing the half-edge R1, v1, is the “first” vertex.


## 3. The Partition

LetUg,n denote the set of planted, unicellular maps of genus g, having n(np) edges. In particular, let ϵ denote the unicellular map of genus zero, containing no (np) edge. This map contains only one edge, the plant, and one additional (np) vertex.Letug+2,n+2=(H,α,γ)∈Ug+2,n+2 with face
(7)γ=[R1,1,2,…,2n+3,2n+4,S1].Then(8)v1=(h11,h12,h13…,h1m),forsomem>0,
where h11=R1. Thus α(h12)=1 and γ=[R1,α(h12),2,…,2n+3,2n+4,S1]. In the following we will identify a partition of Ug+2,n+2 that shall facilitate our main result (Theorem 11).We consider form≥3 the four half edges h12, α(h12), h13 and α(h13). Clearly, α∘σ(h12)=α(h13), whence h12<γα(h13). Furthermore, by construction,
(9)α(h12)<γh12,α(h12)<γh13,h12<γα(h13);
see also Figure 1. Accordingly, there are the following two scenarios:
(10)(A)α(h12)<γh12<γα(h13)<γh13,(B)α(h12)<γh13<γh12<γα(h13).
The case m=2 belongs to scenario (A), which then reduces to
(11)α(h12)<γh12.
This generates the bipartition of Ug+2,n+2,
(12)Ug+2,n+2=Ug+2,n+2A∪˙Ug+2,n+2B.Figure 1
The three branches (red, blue, and black) together with the two pairs(α(h12),h12) and (α(h13),h13).We next refineUg+2,n+2A: for ug+2,n+2∈Ug+2,n+2A, we consider the cycle
(13)γ¯=(α(h12),2,…,h12,α(h13),…,h13,h13+1,…,2(n+1)),
and we use (α(h1i),h1i),i=2,3 to split γ¯ into three branches γ¯1, γ¯2, and γ¯3, where
(14)γ¯1=(α(h12),2,…,h12),γ¯2=(α(h13),…,h13),γ¯3=(h13+1,…,2(n+1));
see Figure 1.Suppose the restrictionα|S is a well-defined fixed-point free involution, and then we call S closed. Similarly, the sets Hγ1,…,γr and Hγ¯i, i=1,2,3 are called closed, if α|Hγ1,…,γr and α|Hγ¯i are fixed-point free involutions.LetUg+2,n+2II denote the subset of Ug+2,n+2A elements in which no Hγ¯i is closed and let Ug+2,n+2I denote its complement. Then
(15)Ug+2,n+2A=Ug+2,n+2I∪˙Ug+2,n+2II.
We refine Ug+2,n+2I further by considering how many branches γi¯,i=1,2,3 the cycle γ contains: (i)
Ug+2,n+21: the set of Ug+2,n+2I elements such that exactly two γ¯i,γ¯j are empty,(ii)
Ug+2,n+22: the set of Ug+2,n+2I elements such that exactly one γ¯i is empty,(iii)
Ug+2,n+2>2: the complement of Ug+2,n+21 and Ug+2,n+22, that is, the set of Ug+2,n+2I such that no γ¯i is empty.Thus(16)Ug+2,n+2I=Ug+2,n+21∪˙Ug+2,n+22∪˙Ug+2,n+2>2.We refineUg+2,n+2>2 a bit more; for this purpose,(i)
letUg+2,n+2>2,3 be the subset of Ug+2,n+2>2 elements where γ¯1=(α(h12),h12),(ii)
letUg+2,n+2>2,4 be the subset of Ug+2,n+2>2-elements where γ¯1=(α(h12),k12,…,k1m), m≥4 and γ¯2=(α(h13),h13),(iii)
letUg+2,n+25 be the complement of Ug+2,n+2>2,3 and Ug+2,n+2>2,4, that is, subset of Ug+2,n+2>2 elements where
(17)γ¯1=(α(h12),k12,…,k1m),γ¯2=(α(h13),k22,…,k2l),m,l≥4.Accordingly,(18)Ug+2,n+2>2=Ug+2,n+25∪˙Ug+2,n+2>2,3∪˙Ug+2,n+2>2,4.Furthermore we presentUg+2,n+2>2,3:
(19)Ug+2,n+2>2,3=Ug+2,n+23∖Ug+2,n+2m,1,
where (i)
Ug+2,n+23 denotes the subset of Ug+2,n+2I elements with γ¯1=(α(h12),h12),(ii)
Ug+2,n+2m,1 denotes the subset of Ug+2,n+22 elements with γ¯1=(α(h12),h12).We writeUg+2,n+2>2,4 as
(20)Ug+2,n+2>2,4=Ug+2,n+24∖(Ug+2,n+2m,2∪˙Ug+2,n+2m,3),
where (i)
Ug+2,n+24 is the subset of Ug+2,n+2I elements with γ¯2=(α(h13),h13),(ii)
Ug+2,n+2m,2 is the subset of Ug+2,n+22 elements with γ¯2=(α(h13),h13),(iii)
Ug+2,n+2m,3 is the subset of Ug+2,n+2>2 elements with γ¯1=(α(h12),h12) and γ¯2=(α(h13),h13).


## 4. Some Lemmas

In this section we state three procedures that are employed repeatedly in our bijection. They are subsequently referred to as “cutting,” “contracting,” and “deleting.” These procedures constitute the key three operations that, applied in various contexts, eventually facilitate the bijection.Lemma 3 (cutting).
Suppose we are given a planted, unicellular mapu=(H,α,γ)∈Ug+2,n+2A with
(21)γ=(R1,α(h12),…,h12,α(h13),…,h13,h13+1,hhh…,2(n+2),S1).
Then u can be mapped to a planted, 3-cellular map, x3,n+2∈X3(n+2), with the three faces γ1,γ2, and γ3 via
(22)c2:Ug+2,n+2A⟶X3(n+2),(H,α,γ)↦(H,α,(γ1,γ2,γ3)),
where
(23)γ1=(R1,1,…,m1,S1),γ2=(R2,m1+1,…,m2,S2),γ3=(R3,m2+1,…,m3,S3).c2 has the following inverse:
(24)g2:X3(n+2)⟶Ug+2,n+2A(H,α,(γ1,γ2,γ3))↦(H,α,γ).Proof.
By assumption we have(25)α(h12)<γh12<γα(h13)<γh13,
whence the face of ug+2,n+2 can be written as in (21). We use (α(h1i),h1i),i=2,3 and γ¯i,i=1,2,3, which are given by (14), then concatenate the sequence of half-edges of (R1), γ¯3, and (S1) to form
(26)γ1=γ¯1,γ2=γ¯2,γ3=(R1,h13+1,…,2(n+2),S1)
and relabel the cycles as in (23). This produces the plants (S1), (S2), and (S3). Since ∏i=13‍γi∈S2n+2, c2(H,α,γ) is a 3-cellular map and accordingly c2 is welldefined, see Figure 2.
We next construct an explicit inverse ofc2. Suppose we are given a 3-cellular map c2((H,α,γ)), in which the γi are as in (26). Then we concatenate the sequences of half-edges of the three γi-cycles and relabel as in (21); that is, γ(h12)=α(h13), γ(h13)=h13+1, and γ(R1)=h13+1. We derive, by construction,
(27)α(h12)<γh12<γα(h13)<γh13.
Accordingly, g2(c2(H,α,γ))=(H,α,γ) is a unicellular map of genus (g+2) with property (A).Figure 2
The mappingsc2 and g2.Lemma 4 (contraction).
Supposeu∈Ug+2,n+2 has a one-sided edge (α(h1l1),h1l1), α(h1l1)<γh1l1, such that α(h1l1) and h1l1 are incident to two different vertices vj,v1. Relabeling the two half-edges we can write the face:
(28)γ=(R1,K1,α(h1l1),K2,h1l1,K3,S1).
Here eitherK1=k11,…,k1n1 or K1=∅, K2=k21,…,k2n2 or K2=∅ and either K3=k31,…,k3n3 or K3=∅. Then u corresponds to a unicellular map u′ together with two distinguished half-edges via mapping
(29)m2:Ug+2,n+2⟶Ug+2,n+1,((H,α,γ),(α(h1l1),h1l1))↦((H′,α′,γ′),(α(h1l1)-1,h1l1-1)),
where H′=H∖{h1l1,α(h1l1)}, α′=α∖{h1l1,α(h1l1)}, γ′=(R1,K1,K2,K3,S1) and α(h1l1)-1=k1n1,h1l1-1=k2n2, if K1,K2≠∅; α(h1l1)-1=h1l1-1=k1n1, if K1≠∅ and K2=∅; α(h1l1)-1=R1, h1l1-1=k2n1, if K1=∅ and K2≠∅; and finally α(h1l1)=h1l1=R1, if K1,K2=∅.
Furthermore,(30)e2:Ug+2,n+1⟶Ug+2,n+2,((H′,α′,γ′),(α(h1l1)-1,h1l1-1))↦((H,α,γ),(α(h1l1),h1l1))
has the property e2∘m2=id.Proof.
m
2
(
(
H
,
α
,
γ
)
,
(
α
(
h
1
l
1
)
,
h
1
l
1
)
) is by construction unicellular and retains the genus of (H,α,γ).We describe the contraction in Figure3.Figure 3
The mappingsm2 and e2. The edge (α(h1l1),h1l1) (green) is one-sided edge.Lemma 5 (deletion).
Given a unicellular mapu=(H,α,γ)∈Ug+2,n+2B with face
(31)γ=(R1,α(h12),K1,h13,K2,h12,α(h13),K3,S1),
where K1=k11,…,k1n1 or K1=∅, K2=k21,…,k2n2 or K2=∅ and K3=k31,…,k3n3 or K3=∅.
Thenu corresponds to a unicellular map u′=(H′,α′,γ′)∈Ug+1,n together with two half-edges kl1 and kl2, where kl1≤γkl2, via the mapping
(32)r2:Ug+2,n+2B⟶Ug+1,n((H,α,γ))↦((H′,α′,γ′),(kl1,kl2)),
where H′=H∖{α(h12),h12,α(h13),h13}, α′=α∖{(h12,α(h12)),(h13,α(h13))} and
(33)γ′=(R1,K2,K1,K3,S1).r2 can be reversed by mapping a unicellular map u=(H,α′,γ′), together with two arbitrary half-edges kl1 and kl2 (kl1≤γkl2) as follows:
(34)s2:Ug+1,n⟶Ug+2,n+2B,((H′,α′,γ′),(kl1,kl2))↦(H,α,γ).Proof.
By construction,γ′∈S2n, α′ is a fixed-point free involution and H′ has cardinality 2n, whence r2((H,α,γ)) is unicellular. Euler characteristic implies that the genus of r2((H,α,γ)) is (g-1). Moreover, we set
(35)kl1=k1n1,kl2=k2n2ifK1,K2≠∅,kl1=kl2=k1n1ifK1≠∅,K2=∅,kl1=R1,kl2=k2n1ifK1=∅,K2≠∅,kl1=kl2=R1ifK1,K2=∅;
see Figure 4.
Given a unicellular map(H′,α′,γ′)∈Ug+1,n, there are
(36)(2n+12)+(2n+11)=(2n+1)(n+1)
ways to choose (kl1,kl2) such that kl1≤γkl2. We now select two half-edges (kl1,kl2) such that kl1≤γkl2 and insert the pairs of half-edges (α(h1i),h1i), i=2,3 into the face γ′. This produces the face γ, with γ(R1)=α(h12), γ(kl2)=h12, γ(kl1)=h13 and γ(h12)=α(h13), γ(h13)=γ′(R1) and γ(α(h13))=γ′(kl2). Consequently we have
(37)γ=(R1,α(h12),…,kl1,h13,…,kl2,h12,α(h13),…,S1).
We then relabel γ as in (31). Since α is a fixed-point free involution and H is a set of cardinality 2(n+2), s2(H′,α′,σ′) is a unicellular map with property B. Euler characteristic implies s2(H′,α′,σ′) has genus (g+2). By construction, we have s2∘r2=idUg+2,n+2B.Figure 4
The mappingsr2 and s2. The deleting edges are (α(h12),h12) (blue) and (α(h13),h13) (red). The gray dashed lines denote a sequence of half-edges connecting two vertices.


## 5. The Main Theorem

In this section we state some auxiliary bijections and our main result. We furthermore give in Figure5 a modular description of how our bijection works.Figure 5
Applying the bijections.We call a planted2-cellular map, whose combinatorial graph is connected, a planted, bicellular map. Let Bg,n denote the set of planted, bicellular maps of genus g with n(np)-edges.LetUg+2,n+25,i denote the subset of Ug+2,n+25 in which only a single Hγ¯i, i=1,2,3 is closed and let Ug+2,n+25,4 denote the set of Ug+2,n+25 elements in which all Hγ¯i, i=1,2,3 are closed, that is, Ug+2,n+25=∪˙i=04Ug+2,n+25,i.Lemma 6.
We have the bijections(38)η5,i:Ug+2,n+25,i⟶⋃0≤g3≤g+1,0≤j,k≤n˙(Ug3,j×Bg+1-g3,n-j),hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh1≤i≤3;η5,4:Ug+2,n+25,4⟶⋃0≤g1,g2≤g+2,0≤j,k≤n‍Ug1,j×Ug2,k×Ug+2-g1-g2,n-j-k.We prove Lemma6 in Section 6.Lemma 7.
We have the four bijections:(39)η1:Ug+2,n+21⟶Ug+2,n+1,η2:Ug+2,n+22⟶Ug+2,n+1,η3:Ug+2,n+23⟶Ug+2,n+1,η4:Ug+2,n+24⟶Ug+2,n+1.We prove Lemma7 in Section 6.Lemma 8.
We have the three bijections:(40)η5:Ug+2,n+2m,1⟶Ug+2,n,η6:Ug+2,n+2m,2⟶Ug+2,n,η7:Ug+2,n+2m,3⟶Ug+2,n.We prove Lemma8 in Section 6.LetTg,n denote the set of planted, tricellular maps of genus g with n(np) edges.Proposition 9.
There is a bijection:(41)θ:Ug+2,n+2II⟶Tg,n.We prove Proposition9 in Section 6.Proposition 10.
There is a bijection(42)ψ:Ug+2,n+2B⟶(2n+1)(n+1)Ug+1,n.We prove Proposition9 in Section 6. In Figure 5 we give an overview of how the above bijections are applied.For a setAg,nξ we denote its cardinality by agξ(n).Theorem 11.
Consider(43)ug+2(n+2)=tg(n)+dg+2(n)+4ug+2(n+1)-3ug+2(n)+(n+1)(2n+1)ug+1(n),
where
(44)dg+2(n)=3∑g1=0g+1∑0≤m≤nug1*(m)bg+1-g1(n-m)+∑g1∑g2∑m1≥0∑m2≥0ug1*(m1)ug2*hhhhhhhhhhhhhh×(m2)ug+2-g1-g2*(n-m1-m2),
with
(45)ug*(n)={0,forg=0,n=0;ug(n),otherwise.


## 6. Proofs

### 6.1.  Proof of Lemma6

Proof.
Consider the following.
Claim  1. The mapping:
(46)η5,1:Ug+2,n+25,1⟶⋃0≤g3≤g+1,0≤j,k≤n˙(Ug3,j×Bg+1-g3,n-j),ug+2,n+2↦(ug3,j,bg+1-g3,n-j),0≤g3≤g+1,hhhhhh1≤j≤n,
is a bijection. We first prove that η5,1 is welldefined. For a planted unicellular map (H,α,γ)=ug+2,n+2∈Ug+2,n+25,1 with face
(47)γ=(R1,α(h12),…,h12,α(h13),…,hhhh13,h13+1,…,2(n+2),S1),
we employ the mapping c2 of the Cutting-Lemma (Lemma 3) in order to decompose ug+2,n+2 into a planted 3-cellular map, x3,n+2=(H,α,(γi)1≤i≤3), where
(48)γ1=γ¯1,γ2=γ¯2,γ3=(R1,h13+1,…,2(n+2),S1),
where γ3 is obtained by concatenating the sequence of half-edges of (R1), γ¯3, and (S1).
For any(H,α,γ)=ug+2,n+2∈Ug+2,n+25,1, Hγ¯1 is closed. Since γ1=γ¯1, the restriction α|Hγ1 is a fixed-point free involution. Accordingly, (Hγ1,α|Hγ1,γ1) is a planted unicellular map.
SinceHγ¯2∪Hγ¯3 is closed and γi, i=2,3 is given in (48), the restriction α|Hγ1,γ2 is a well-defined fixed-point free involution. Furthermore, since neither Hγ¯2 nor Hγ¯3 are closed, Hγ2 and Hγ3 are not closed either. Therefore (Hγ1,γ2,α|Hγ1,γ2,(γi)1≤i≤2) is a planted bicellular map with the plants (S1) and (h13).
Letug3,j=(Hγ1,α|Hγ1,γ1) and bg′,n′=(Hγ1,γ2,α|Hγ1,γ2,(γi)1≤i≤2).
Supposeug+2,n+2, ug3,j, and bg′,n′ have J, Jγ1 and Jb vertices, respectively. Then 2-2(g+2)=J-(n+2)+1 and 2-2g3=Jγ1-j+1, whence
(49)2-2(g+1-g3)=J-Jγ1-(n-j)+2.
Since the edges incident to plants and plants do not contribute to the number of edges and vertices, we have n′=n-j,1≤j≤n, Jb=J-Jγ1. As a result bg′,n′ has genus (g+1-g3), where 0≤g3≤g+1, whence η5,1 is well-defined.
We next show thatη5,1 is injective. In order to apply the mapping c2 of the Cutting-Lemma, we introduce
(50)ζ5,1((Hγ1,α|Hγ1,γ1),(Hγ1,γ2,α|Hγ1,γ2,(γi)1≤i≤2))=(H,α,(γi)1≤i≤3),
where γi are given by (48), α=α|Hγ1,γ2,γ3, and H=Hγ1∪Hγ1,γ2.
For any(51)η5,1((H,α,γ))=(ug3,j,bg+1-g3,n-j)∈⋃0≤g3≤g+1,0≤j≤n˙(Ug3,j×Bg+1-g3,n-j),
where ug3,j=(Hγ1,α|Hγ1,γ1), and bg+1-g3,n-j=(Hγ1,γ2,α|Hγ1,γ2,(γi)1≤i≤2), we apply ζ5,1. This generates the 3-cellular map (H,α,(γi)1≤i≤3). Since ug3,j has j edges and bg+1-g3,n-j has (n-j) edges, and the process generates the edges (α(h12),h12) and (α(h13),h13), we have x3,n+2=(H,α,(γi)1≤i≤3)∈X3(n+2). We can now apply c2 of Lemma 3, which induces the mapping c5,1:X3(n+2)→Ug+2,n+25,1. Lemma 3 now implies furthermore
(52)(c5,1∘ζ5,1)∘η5,1=id,
whence the mapping η5,1 is injective.
It thus remains to prove thatη5,1 is surjective. This follows again from close inspection of the proof of the Lemma 3, which implies
(53)η5,1∘(c5,1∘ζ5,1)=id.
Therefore, η5,1 is surjective and Claim  1 is completed.
Analogously we prove thatη5,2 and η5,3 are injective.
Claim  2. The mapping:(54)η5,4:Ug+2,n+25,4⟶⋃0≤g1,g2≤g+2,0≤j,k≤n‍Ug1,j×Ug2,k×Ug+2-g1-g2,n-j-k,ug+2,n+2↦(ug1,j,ug2,k,ug+2-g1-g2,n-j-k),
with 1≤g1,g2≤g+2 and 1≤j,k≤n is a bijection.
We first show thatη5,4 is well-defined. As in the proof of Claim  1, we employ the Cutting-Lemma which produces a 3-cellular map with the boundary components (γ1,γ2,γ3).
For anyug+2,n+2∈Ug+2,n+25,4, each of the Hγ¯i is closed. Thus the restrictions α|Hγi, for i=1,2,3, are welldefined and fixed-point free involutions. As a result, (Hγ1,α|Hγ1,γ1), (Hγ1,α|Hγ2,γ2), and (Hγ1,α|Hγ3,γ3) are unicellular maps, respectively.
Let(55)ug1,j=(Hγ1,α|Hγ1,γ1),ug2,k=(Hγ2,α|Hγ2,γ2),ug′,n′=(Hγ3,α|Hγ3,γ3).
Suppose thatug+2,n+2, ug1,j, ug2,k, and ug′,n′ have J, Jγ1, Jγ2, and Jγ3 vertices, respectively. Then
(56)2-2(g+2)=J-(n+2)+1,2-2g1=Jγ1-j+1,2-2g2=Jγ2-k+1,1≤j,k≤n.
Furthermore, we have
(57)J-Jγ1-Jγ2-(n-j-k)+1=2-2(g+2-g1-g2).
After applying the Cutting-Lemma, (h12) and (h13) become plants, similarly (α(h12),h12) and (α(h13),h13) become edges incident to plants. Thus, we have n′=n-j-k,0≤j,k≤n and Jγ3=J-2-Jγ1-Jγ2 and accordingly obtain
(58)J-2-Jγ1-Jγ2-(n-j-k)+1=2-2(g+2-g1-g1).
Consequently, ug′,n′ has genus (g+2-g1-g2), where 0≤g1,g2≤g+2, and η5,4 is well defined.
We next proveη5,4 is injective. We establish this as in Claim  1, introducing
(59)ζ5,4:((Hγ1,α|Hγ1,γ1),(Hγ2,α|Hγ2,γ2),(Hγ3,α|Hγ3,γ3))↦(H,α,(γi)1≤i≤3),
where γi is given in (48), α=α|Hγ1,γ2,γ3, and H=Hγ1∪Hγ1,γ2. Analogously, c2 of Lemma 3 induces the mapping c5,4 and
(60)(c5,4∘ζ5,4)∘η5,4=id,
whence the mapping η5,4 is injective.
Subjectivity ofη5,4 is implied by the Cutting-Lemma which guarantees
(61)η5,4∘(c5,4∘ζ5,4)=id,
whence Claim 2 and the proof of the lemma are complete.


### 6.2.  Proof of Proposition9

Proof.
We prove that the mapping(62)θ:Ug+2,n+2II⟶Tg,n,ug+2,n+2↦tg,n,
is a bijection. As for well definedness, suppose ug+2,n+2∈Ug+2,n+2II where
(63)γ=(R1,α(h12),…,h12,α(h13),…,hhhh13,h13+1,…,2(n+1),S1).
We use mapping c2 of the Cutting-Lemma and derive the planted 3-cellular map, x3,n+2=(H,α,(γi)1≤i≤3), where
(64)γ1=γ¯1,γ2=γ¯2,γ3=(R1,h13+1,…,2(n+1),S1).
Here γ3 is obtained by concatenating the sequence of half-edges contained in (R1), γ¯3 and (S1).
Forug+2,n+2∈Ug+2,n+2II none of the Hγ¯i, i=1,2,3 is closed, whence the associated combinatorial graph of x3,n+2 is connected. Accordingly, x3,n+2=θ(ug+2,n+2) is a planted tricellular map with plants (h12), (h13), and (S1). Euler's characteristic formula implies tg,n has genus g and n edges, whence θ is well defined. Injectivity and surjectivity of θ are implied by the Cutting Lemma.


### 6.3.  Proof of Lemma7

Proof.
Consider the following.
Claim  1. The mapping:
(65)η1:Ug+2,n+21⟶Ug+2,n+1,((H,α,γ),(α(h12),h12))↦((H′,α′,γ′),(α(h12)-1,h12-1)),
is a bijection.
The contraction lemma implies thatη1 is well defined. Injectivity of η1 follows by considering the mapping ρ1 induced by the mapping e2 of Lemma 4, where ρ1((H′,α′,γ′))=(H,α,γ)∈Ug+2,n+21. Lemma 4 guarantees ρ1∘η1=id, whence η1 is injective. Surjectivity of η1 is a consequence of η1∘ρ1=id, implied by Lemma 4; see Figure 6.
The proof thatηj:Ug+2,n+2j→Ug+2,n+1 is a bijection for j=2,3,4 follows analogously; see Figure 7.Figure 6
The mappingη1 and the one-sided edge (α(h12),h12)) (green).Figure 7
The mappingsη2, η3, and η4.


### 6.4. The Proof of Lemma8

Proof.
Consider the following.
Claim  1. The mapping:
(66)η5:Ug+2,n+2m,1⟶Ug+2,n,((H,α,γ),(α(h12),h12),(α(h13),h13))mmm↦((H′,α′,γ′),(α(h12)-1,h12-1)mmmmmmm(α(h13)-1,h13-1)),
is a bijection.
We first prove thatη5 is well defined. Consider (H,α,γ)∈Ug+2,n+2m,1 together with two one-sided edges, (α(h12),h12), (α(h13),h13), such that h11 and h12 are incident to v1, α(h11) and α(h12) are incident to vi and vj.
We then apply Lemma4 to a (H,α,γ)∈Ug+2,n+2m,1 together with the one-side edge (α(h12),h12). We iterate applying Lemma 4 w.r.t. the edge (α(h13),h13). By definition of Lemma 4 this generates the unicellular map (H′,α′,γ′) of genus (g+2) having n edges with distinguished four half-edges α(h12)-1, h12-1, α(h13)-1 and h13-1.
Since Lemma4 preserves genus, η5((H,α,γ)) has genus (g+2) and n edges, whence η5 is well defined.
We next proveη5 is injective. Suppose we have a unicellular map (H′,α′,γ′)∈Ug+2,n with four distinguished half-edges α(h12)-1, h12-1, α(h13)-1, and h13-1. We observe that the mapping m2 constructed in Lemma 4 allows us to obtain a mapping ρ5:Ug+2,n→Ug+2,n+2m,1 such that
(67)ρ5∘η5=id,
whence injectivity.
Surjectivity follows by computingη5∘ρ5=id.
The proof that(68)η6:Ug+2,n+2m,2⟶Ug+2,n,η7:Ug+2,n+2m,3⟶Ug+2,n
are bijections is analogous; see Figure 8.Figure 8
The mappingsη5, η6 and η7.


### 6.5. The Proof of Proposition10

Proof.
Proposition10 follows directly from Lemma 5.


### 6.6.  The Proof of Theorem11

Proof.
According to Lemmas6, 7, and 8 and Propositions 9 and 10, we have (i)
ug+20,i(n+2)=ug+2(n+1), for 1≤i≤4,(ii)
ug+2i(n+2)=ug+2(n+1), for 1≤i≤4,(iii)
ug+2m,j(n+2)=ug+2(n), for 1≤j≤3,(iv)
ug+2II(n+2)=tg(n),(v)
ug+2B(n+2)=(n+1)(2n+1)ug+1(n).
According to (12), (15), and (16) we have
(69)ug+2,n+2=ug+2I(n+2)+ug+2II(n+2)+ug+2B(n+2)=1+2ug+2(n+1)+ug+2>2(n+2)+tg(n)+(n+1)(2n+1)ug+1(n).
Furthermore, according to (18), (19), and (20), we have
(70)ug+2>2(n+2)=ug+25(n+2)+ug+2>2,3(n+2)+ug+2>2,4(n+2)=dg+2(n)+2ug+2(n+1)-3ug+2(n),
which establishes (43).


## 6.1.  Proof of Lemma6

Proof.
Consider the following.
Claim  1. The mapping:
(46)η5,1:Ug+2,n+25,1⟶⋃0≤g3≤g+1,0≤j,k≤n˙(Ug3,j×Bg+1-g3,n-j),ug+2,n+2↦(ug3,j,bg+1-g3,n-j),0≤g3≤g+1,hhhhhh1≤j≤n,
is a bijection. We first prove that η5,1 is welldefined. For a planted unicellular map (H,α,γ)=ug+2,n+2∈Ug+2,n+25,1 with face
(47)γ=(R1,α(h12),…,h12,α(h13),…,hhhh13,h13+1,…,2(n+2),S1),
we employ the mapping c2 of the Cutting-Lemma (Lemma 3) in order to decompose ug+2,n+2 into a planted 3-cellular map, x3,n+2=(H,α,(γi)1≤i≤3), where
(48)γ1=γ¯1,γ2=γ¯2,γ3=(R1,h13+1,…,2(n+2),S1),
where γ3 is obtained by concatenating the sequence of half-edges of (R1), γ¯3, and (S1).
For any(H,α,γ)=ug+2,n+2∈Ug+2,n+25,1, Hγ¯1 is closed. Since γ1=γ¯1, the restriction α|Hγ1 is a fixed-point free involution. Accordingly, (Hγ1,α|Hγ1,γ1) is a planted unicellular map.
SinceHγ¯2∪Hγ¯3 is closed and γi, i=2,3 is given in (48), the restriction α|Hγ1,γ2 is a well-defined fixed-point free involution. Furthermore, since neither Hγ¯2 nor Hγ¯3 are closed, Hγ2 and Hγ3 are not closed either. Therefore (Hγ1,γ2,α|Hγ1,γ2,(γi)1≤i≤2) is a planted bicellular map with the plants (S1) and (h13).
Letug3,j=(Hγ1,α|Hγ1,γ1) and bg′,n′=(Hγ1,γ2,α|Hγ1,γ2,(γi)1≤i≤2).
Supposeug+2,n+2, ug3,j, and bg′,n′ have J, Jγ1 and Jb vertices, respectively. Then 2-2(g+2)=J-(n+2)+1 and 2-2g3=Jγ1-j+1, whence
(49)2-2(g+1-g3)=J-Jγ1-(n-j)+2.
Since the edges incident to plants and plants do not contribute to the number of edges and vertices, we have n′=n-j,1≤j≤n, Jb=J-Jγ1. As a result bg′,n′ has genus (g+1-g3), where 0≤g3≤g+1, whence η5,1 is well-defined.
We next show thatη5,1 is injective. In order to apply the mapping c2 of the Cutting-Lemma, we introduce
(50)ζ5,1((Hγ1,α|Hγ1,γ1),(Hγ1,γ2,α|Hγ1,γ2,(γi)1≤i≤2))=(H,α,(γi)1≤i≤3),
where γi are given by (48), α=α|Hγ1,γ2,γ3, and H=Hγ1∪Hγ1,γ2.
For any(51)η5,1((H,α,γ))=(ug3,j,bg+1-g3,n-j)∈⋃0≤g3≤g+1,0≤j≤n˙(Ug3,j×Bg+1-g3,n-j),
where ug3,j=(Hγ1,α|Hγ1,γ1), and bg+1-g3,n-j=(Hγ1,γ2,α|Hγ1,γ2,(γi)1≤i≤2), we apply ζ5,1. This generates the 3-cellular map (H,α,(γi)1≤i≤3). Since ug3,j has j edges and bg+1-g3,n-j has (n-j) edges, and the process generates the edges (α(h12),h12) and (α(h13),h13), we have x3,n+2=(H,α,(γi)1≤i≤3)∈X3(n+2). We can now apply c2 of Lemma 3, which induces the mapping c5,1:X3(n+2)→Ug+2,n+25,1. Lemma 3 now implies furthermore
(52)(c5,1∘ζ5,1)∘η5,1=id,
whence the mapping η5,1 is injective.
It thus remains to prove thatη5,1 is surjective. This follows again from close inspection of the proof of the Lemma 3, which implies
(53)η5,1∘(c5,1∘ζ5,1)=id.
Therefore, η5,1 is surjective and Claim  1 is completed.
Analogously we prove thatη5,2 and η5,3 are injective.
Claim  2. The mapping:(54)η5,4:Ug+2,n+25,4⟶⋃0≤g1,g2≤g+2,0≤j,k≤n‍Ug1,j×Ug2,k×Ug+2-g1-g2,n-j-k,ug+2,n+2↦(ug1,j,ug2,k,ug+2-g1-g2,n-j-k),
with 1≤g1,g2≤g+2 and 1≤j,k≤n is a bijection.
We first show thatη5,4 is well-defined. As in the proof of Claim  1, we employ the Cutting-Lemma which produces a 3-cellular map with the boundary components (γ1,γ2,γ3).
For anyug+2,n+2∈Ug+2,n+25,4, each of the Hγ¯i is closed. Thus the restrictions α|Hγi, for i=1,2,3, are welldefined and fixed-point free involutions. As a result, (Hγ1,α|Hγ1,γ1), (Hγ1,α|Hγ2,γ2), and (Hγ1,α|Hγ3,γ3) are unicellular maps, respectively.
Let(55)ug1,j=(Hγ1,α|Hγ1,γ1),ug2,k=(Hγ2,α|Hγ2,γ2),ug′,n′=(Hγ3,α|Hγ3,γ3).
Suppose thatug+2,n+2, ug1,j, ug2,k, and ug′,n′ have J, Jγ1, Jγ2, and Jγ3 vertices, respectively. Then
(56)2-2(g+2)=J-(n+2)+1,2-2g1=Jγ1-j+1,2-2g2=Jγ2-k+1,1≤j,k≤n.
Furthermore, we have
(57)J-Jγ1-Jγ2-(n-j-k)+1=2-2(g+2-g1-g2).
After applying the Cutting-Lemma, (h12) and (h13) become plants, similarly (α(h12),h12) and (α(h13),h13) become edges incident to plants. Thus, we have n′=n-j-k,0≤j,k≤n and Jγ3=J-2-Jγ1-Jγ2 and accordingly obtain
(58)J-2-Jγ1-Jγ2-(n-j-k)+1=2-2(g+2-g1-g1).
Consequently, ug′,n′ has genus (g+2-g1-g2), where 0≤g1,g2≤g+2, and η5,4 is well defined.
We next proveη5,4 is injective. We establish this as in Claim  1, introducing
(59)ζ5,4:((Hγ1,α|Hγ1,γ1),(Hγ2,α|Hγ2,γ2),(Hγ3,α|Hγ3,γ3))↦(H,α,(γi)1≤i≤3),
where γi is given in (48), α=α|Hγ1,γ2,γ3, and H=Hγ1∪Hγ1,γ2. Analogously, c2 of Lemma 3 induces the mapping c5,4 and
(60)(c5,4∘ζ5,4)∘η5,4=id,
whence the mapping η5,4 is injective.
Subjectivity ofη5,4 is implied by the Cutting-Lemma which guarantees
(61)η5,4∘(c5,4∘ζ5,4)=id,
whence Claim 2 and the proof of the lemma are complete.


## 6.2.  Proof of Proposition9

Proof.
We prove that the mapping(62)θ:Ug+2,n+2II⟶Tg,n,ug+2,n+2↦tg,n,
is a bijection. As for well definedness, suppose ug+2,n+2∈Ug+2,n+2II where
(63)γ=(R1,α(h12),…,h12,α(h13),…,hhhh13,h13+1,…,2(n+1),S1).
We use mapping c2 of the Cutting-Lemma and derive the planted 3-cellular map, x3,n+2=(H,α,(γi)1≤i≤3), where
(64)γ1=γ¯1,γ2=γ¯2,γ3=(R1,h13+1,…,2(n+1),S1).
Here γ3 is obtained by concatenating the sequence of half-edges contained in (R1), γ¯3 and (S1).
Forug+2,n+2∈Ug+2,n+2II none of the Hγ¯i, i=1,2,3 is closed, whence the associated combinatorial graph of x3,n+2 is connected. Accordingly, x3,n+2=θ(ug+2,n+2) is a planted tricellular map with plants (h12), (h13), and (S1). Euler's characteristic formula implies tg,n has genus g and n edges, whence θ is well defined. Injectivity and surjectivity of θ are implied by the Cutting Lemma.


## 6.3.  Proof of Lemma7

Proof.
Consider the following.
Claim  1. The mapping:
(65)η1:Ug+2,n+21⟶Ug+2,n+1,((H,α,γ),(α(h12),h12))↦((H′,α′,γ′),(α(h12)-1,h12-1)),
is a bijection.
The contraction lemma implies thatη1 is well defined. Injectivity of η1 follows by considering the mapping ρ1 induced by the mapping e2 of Lemma 4, where ρ1((H′,α′,γ′))=(H,α,γ)∈Ug+2,n+21. Lemma 4 guarantees ρ1∘η1=id, whence η1 is injective. Surjectivity of η1 is a consequence of η1∘ρ1=id, implied by Lemma 4; see Figure 6.
The proof thatηj:Ug+2,n+2j→Ug+2,n+1 is a bijection for j=2,3,4 follows analogously; see Figure 7.Figure 6
The mappingη1 and the one-sided edge (α(h12),h12)) (green).Figure 7
The mappingsη2, η3, and η4.


## 6.4. The Proof of Lemma8

Proof.
Consider the following.
Claim  1. The mapping:
(66)η5:Ug+2,n+2m,1⟶Ug+2,n,((H,α,γ),(α(h12),h12),(α(h13),h13))mmm↦((H′,α′,γ′),(α(h12)-1,h12-1)mmmmmmm(α(h13)-1,h13-1)),
is a bijection.
We first prove thatη5 is well defined. Consider (H,α,γ)∈Ug+2,n+2m,1 together with two one-sided edges, (α(h12),h12), (α(h13),h13), such that h11 and h12 are incident to v1, α(h11) and α(h12) are incident to vi and vj.
We then apply Lemma4 to a (H,α,γ)∈Ug+2,n+2m,1 together with the one-side edge (α(h12),h12). We iterate applying Lemma 4 w.r.t. the edge (α(h13),h13). By definition of Lemma 4 this generates the unicellular map (H′,α′,γ′) of genus (g+2) having n edges with distinguished four half-edges α(h12)-1, h12-1, α(h13)-1 and h13-1.
Since Lemma4 preserves genus, η5((H,α,γ)) has genus (g+2) and n edges, whence η5 is well defined.
We next proveη5 is injective. Suppose we have a unicellular map (H′,α′,γ′)∈Ug+2,n with four distinguished half-edges α(h12)-1, h12-1, α(h13)-1, and h13-1. We observe that the mapping m2 constructed in Lemma 4 allows us to obtain a mapping ρ5:Ug+2,n→Ug+2,n+2m,1 such that
(67)ρ5∘η5=id,
whence injectivity.
Surjectivity follows by computingη5∘ρ5=id.
The proof that(68)η6:Ug+2,n+2m,2⟶Ug+2,n,η7:Ug+2,n+2m,3⟶Ug+2,n
are bijections is analogous; see Figure 8.Figure 8
The mappingsη5, η6 and η7.


## 6.5. The Proof of Proposition10

Proof.
Proposition10 follows directly from Lemma 5.


## 6.6.  The Proof of Theorem11

Proof.
According to Lemmas6, 7, and 8 and Propositions 9 and 10, we have (i)
ug+20,i(n+2)=ug+2(n+1), for 1≤i≤4,(ii)
ug+2i(n+2)=ug+2(n+1), for 1≤i≤4,(iii)
ug+2m,j(n+2)=ug+2(n), for 1≤j≤3,(iv)
ug+2II(n+2)=tg(n),(v)
ug+2B(n+2)=(n+1)(2n+1)ug+1(n).
According to (12), (15), and (16) we have
(69)ug+2,n+2=ug+2I(n+2)+ug+2II(n+2)+ug+2B(n+2)=1+2ug+2(n+1)+ug+2>2(n+2)+tg(n)+(n+1)(2n+1)ug+1(n).
Furthermore, according to (18), (19), and (20), we have
(70)ug+2>2(n+2)=ug+25(n+2)+ug+2>2,3(n+2)+ug+2>2,4(n+2)=dg+2(n)+2ug+2(n+1)-3ug+2(n),
which establishes (43).



---

*Source: 712431-2013-12-08.xml*