Jérémie Bettinelli
email: jeremie.bettinelli@normalesup.org.

Slit-slide-sew bijections for bipartite and quasibipartite plane maps

Keywords: bijection, plane map, bipartite map, quasibipartite map, map enumeration

We unify and extend previous bijections on plane quadrangulations to bipartite and quasibipartite plane maps. Starting from a bipartite plane map with a distinguished edge and two distinguished corners (in the same face or in two different faces), we build a new plane map with a distinguished vertex and two distinguished half-edges directed toward the vertex. The faces of the new map have the same degree as those of the original map, except at the locations of the distinguished corners, where each receives an extra degree. The idea behind this bijection is to build a path from the distinguished elements, slit the map along it, and sew back after sliding by one unit, thus mildly modifying the structure of the map at the extremities of the sliding path. This bijection allows to recover Tutte's famous counting formula for bipartite and quasibipartite plane maps.

In addition, we explain how to decompose the previous bijection into two more elementary ones, which each transfer a degree from one face of the map to another face. In particular, these transfer bijections are simpler to manipulate than the previous one and this point of view simplifies the proofs.

Introduction

This extended abstract of [START_REF] Bettinelli | Slit-slide-sew bijections for bipartite and quasibipartite plane maps[END_REF] is a sequel to [START_REF] Bettinelli | Increasing forests and quadrangulations via a bijective approach[END_REF], in which we presented two bijections on plane quadrangulations with a boundary. In the present work, we show how to generalize these bijections to bipartite and, in some cases, quasibipartite plane maps. Recall that a plane map is an embedding of a finite connected graph (possibly with multiple edges and loops) into the sphere, considered up to orientation-preserving homeomorphisms. It is bipartite if each of its faces have an even degree and quasibipartite if it has two faces of odd degree and all other faces of even degree.

The number of such maps with prescribed face degrees has been computed by several methods. For an r-tuple a = (a 1 , . . . , a r ) of positive integers, let us denote by M(a) the number of plane maps with r numbered faces f 1 , . . . , f r of respective degrees a 1 , . . . , number of plane maps with r numbered faces f 1 , . . . , f r of respective degrees a 1 , . . . , a r , where each face has a marked corner. The r-tuple a will be called the type of such maps (see Figure 1). By elementary considerations and Euler's characteristic formula, the integers

PSfrag replacements

f 1 f 10 f 8 f 3 f 12 f 14 f 11 f 9 f 2 f 13 f 7 f 5 f 4 f 6
E(a) := 1 2 r ∑ i=1 a i and V(a) := E(a) -r + 2 (1.1)
are respectively the numbers of edges and vertices of maps of type a. Solving a technically involved recurrence, Tutte [START_REF] Tutte | A census of slicings[END_REF] showed that, when at most two a i 's are odd, that is, for bipartite or quasibipartite maps,

M(a) = E(a) -1 ! V(a) ! r ∏ i=1 α(a i ),
where α(x) := x! x/2 ! (x -1)/2 ! .

(1.2)

Formula (1.2), commonly referred to as Tutte's formula of slicings, was later recovered by Cori [START_REF] Cori | Planarité et algébricité[END_REF][START_REF] Cori | Un code pour les graphes planaires et ses applications[END_REF] thanks to a so-called transfer bijection, roughly consisting in iteratively transferring one degree from a face to a neighboring face, until the map has a very simple structure. Using a bijective encoding by so-called blossoming trees, Schaeffer [START_REF] Schaeffer | Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees[END_REF] then recovered it in the bipartite case. Finally, we may also obtain it by using the socalled Bouttier-Di Francesco-Guitter bijection [START_REF] Bouttier | Planar maps as labeled mobiles[END_REF], which encodes plane maps by tree-like structures called mobiles: see [START_REF] Collet | A simple formula for the series of constellations and quasi-constellations with boundaries[END_REF] for the computation of related generating functions using this approach.

In the present work, we give a bijective interpretation for the following combinatorial identities, which somehow allows to "grow" maps by adding to a bipartite map two new corners either to the same face or to two different faces.

Proposition 1 (Adding two corners to the same face). Let a = (a 1 , . . . , a r ) be an r-tuple of positive even integers and let ã = ( ã1 , . . . , ãr ) := (a 1 + 2, a 2 , . . . , a r ). Then the following identity holds:

(a 1 + 1) (a 1 + 2) E(a) M(a) = ã1 /2 ( ã1 -1)/2 V( ã) M( ã).

(1.3) a r , where each face has a marked corner. The r-tuple a will be called the type of such maps (see Figure 1). By elementary considerations and Euler's characteristic formula, the integers

E(a) := 1 2 r ∑ i=1 a i and V(a) := E(a) -r + 2 (1.1)
are respectively the numbers of edges and vertices of maps of type a. Solving a technically involved recurrence, Tutte [START_REF] Tutte | A census of slicings[END_REF] showed that, when at most two a i 's are odd, that is, for bipartite or quasibipartite maps,

M(a) = E(a) -1 ! V(a) ! r ∏ i=1 α(a i ), where α(x) := x! x/2 ! (x -1)/2 ! . (1.2)
Formula (1.2), commonly referred to as Tutte's formula of slicings, was later recovered by Cori [START_REF] Cori | Un code pour les graphes planaires et ses applications[END_REF][START_REF] Cori | Planarité et algébricité[END_REF] thanks to a so-called transfer bijection, roughly consisting in iteratively transferring one degree from a face to a neighboring face, until the map has a very simple structure. Using a bijective encoding by so-called blossoming trees, Schaeffer [START_REF] Schaeffer | Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees[END_REF] then recovered it in the bipartite case. Finally, we may also obtain it by using the socalled Bouttier-Di Francesco-Guitter bijection [START_REF] Bouttier | Planar maps as labeled mobiles[END_REF], which encodes plane maps by tree-like structures called mobiles: see [START_REF] Collet | A simple formula for the series of constellations and quasi-constellations with boundaries[END_REF] for the computation of related generating functions using this approach.

In the present work, we give a bijective interpretation for the following combinatorial identities, which somehow allows to "grow" maps by adding to a bipartite map two new corners either to the same face or to two different faces.

Proposition 1 (Adding two corners to the same face). Let a = (a 1 , . . . , a r ) be an r-tuple of positive even integers and let ã = ( ã1 , . . . , ãr ) := (a 1 + 2, a 2 , . . . , a r ). Then the following identity holds:

(a 1 + 1) (a 1 + 2) E(a) M(a) = ã1 /2 ( ã1 -1)/2 V( ã) M( ã). (1.3)
Proposition 2 (Adding one corner to each of two different faces). Let a = (a 1 , . . . , a r ) be an r-tuple of positive even integers and let ã = ( ã1 , . . . , ãr ) := (a 1 + 1, a 2 + 1, a 3 , . . . , a r ). Then the following identity holds:

(a 1 + 1) (a 2 + 1) E(a) M(a) = ã1 /2 ã2 /2 V( ã) M( ã). (1.4)
For the r-tuple (2, . . . , 2), it is easy to see that M(2, . . . , 2) = 2 r-1 (r -1)! as there is only one map with r faces of degree 2 and a chosen first face with its marked corner, and there are (r -1)! ways to order the remaining faces and 2 r-1 ways to choose the remaining marked corners. This initial condition, together with the above propositions and the obvious exchangeability of the coordinates of a provides yet another proof of (1.2).

We will use the technique introduced in [START_REF] Bettinelli | Increasing forests and quadrangulations via a bijective approach[END_REF] of what we call slit-slide-sew bijections, and whose idea is the following. We will interpret the sides of (1.3) and (1.4) as counting maps with some distinguished "elements." More precisely, in each case, the term in M counts maps of some type and the three prefactors will count something whose number only depends on this type: it can be a corner, an edge, a vertex, or something a bit more intricate. For instance, the left-hand side of (1.4) counts maps of type a with a distinguished corner in f 1 , a distinguished corner in f 2 and a distinguished edge (for any i, there are a i + 1 corners in f i because of the already marked corner; see Section 2 for the convention on distinguishing corners).

From a map with its distinguished elements, we first construct a directed path. We then slit the map along this path and we sew back together the sides of the slit but after sliding by one unit. Let us look at a face lying to the left of some edge of the path. Before the operation, it is adjacent to the face lying to the right of the same edge and, after the operation, it is adjacent to the face lying to the right of the next or previous edge along the path. This operation mildly modifies the map along the path but does not affect its faces, except around the extremities of the path. In the process, new distinguished elements naturally appear in the resulting map. Plainly, in order for this operation to work, the path we construct has to be totally recoverable from the new distinguished elements.

We will furthermore see the previous bijections as compositions of two more elementary bijections, which can be thought of as "transferring" a corner from a face, say f r+1 , to another face, say f 1 . In the case where f r+1 has degree 1, it somehow vanishes into a vertex. We chose to use an r + 1-th face for these operations as we will see the previous mappings as compositions of the following ones by using an extra face. More precisely, by a slight modification, we may transform a distinguished edge into an extra degree-2 face and use twice the bijections interpreting the following identities in order to transfer both corners of the extra face to the desired faces.

Proposition 3 (Transferring a corner from a degree at least 2 face). Let a = (a 1 , . . . , a r+1 ) be an r + 1-tuple of positive integers with a r+1 ≥ 2, and either all even or such that only a r+1 and one other coordinate are odd. Let also ã = ( ã1 , . . . , ãr+1 ) := (a 1 + 1, a 2 , . . . , a r , a r+1 -1). Then the following identity holds:

(a 1 + 1) a r+1 /2 M(a) = ã1 /2 ( ãr+1 + 1) M( ã).

(1.5)

Proposition 4 (Transferring a corner from a degree 1-face). Let a = (a 1 , . . . , a r , 1) be an r + 1-tuple of positive integers with two odd coordinates and let ã = ( ã1 , . . . , ãr ) := (a 1 + 1, a 2 , . . . , a r ). Then the following identity holds:

(a 1 + 1) M(a) = ã1 /2 V( ã) M( ã). (1.6)
Related works. Our bijections bear some similarities with two related works. In the papers we mentioned earlier, Cori [START_REF] Cori | Un code pour les graphes planaires et ses applications[END_REF][START_REF] Cori | Planarité et algébricité[END_REF] also transfers one degree from a face to another one. In his approach, he does so in a local way, in the sense that the degree passes from a face to one of its neighbor. In the present work, our transfer bijections are global in the sense that the degree passes from a face to an arbitrarily far away one. Moreover, the notion of geodesic path along which we slide the map is of crucial importance.

In a very recent work, Louf [START_REF] Louf | A new family of bijections for planar maps[END_REF] introduced a new family of bijections accounting for formulas on plane maps arising from the so-called KP hierarchy. His bijections also strongly rely on the mechanism of sliding along a path but, in his case, the path is also somehow local (although arbitrary long) as it is canonically defined from only one vertex using a depth-first search exploration of the map. Another difference of importance is that his mappings may produce two maps as an output, which corresponds to the fact that the formulas in question are quadratic; in the present work, the output is always one map, which corresponds to linear formulas.

Preliminaries

We will use the following terminology. We call half-edge an edge given with one of its two possible orientations. For a half-edge h, we denote by h -its origin, by h + its end, and by rev(h) its reverse (the same edge with the other orientation). We say that a halfedge h is incident to a face f if h lies on the boundary of f and has f to its left. It will be convenient to view corners as half-edges having no origin, only an end. In particular, if c is a corner, we will write c + the vertex corresponding to it. Moreover, we use the convention that distinguishing a corner "splits" it into two new corners: see Figure 2. Definition 1. A path from a vertex v to a vertex v is a finite sequence p = (p 1 , p 2 , . . . , p ) of half-edges such that p - 1 = v, for 1 ≤ k ≤ -1, p + k = p - k+1 , and p + = v . Its length is the integer [p] := . By convention, the empty path has length 0.

A path p is called self-avoiding if it does not meet twice the same vertex. The reverse of p = (p 1 , p 2 , . . . , p ) is rev(p) := (rev(p ), rev(p -1 ), . . . , rev(p 1 )). Let Ô be a path. We denote by Ô i→j the path (Ô i , . . . , Ô j

) if 1 ≤ i ≤ j ≤ [Ô], or the empty path otherwise. If Õ is another path satisfying Õ - 1 = Ô + [Ô] , we set Ô • Õ := (Ô 1 , . . . , Ô [Ô] , Õ 1 , . . . , Õ [Õ] )
the concatenation of Ô and Õ. Throughout this paper, the notion of metric we use is the graph metric: if m is a map, the distance d m (v, v ′ ) between two vertices v and v ′ is the smaller ℓ for which there exists a path of length ℓ from v to v ′ . A geodesic from v to v ′ is such a path. The leftmost geodesic from a corner c to a vertex or to a corner is constructed as follows. First, we consider all the geodesics from c + to the vertex or to the vertex corresponding to the corner. We take the set of all the first steps of these geodesics.

Starting from c, we select the first half-edge to its left that belongs to this set. Then we iterate the process from this half-edge until we reach the desired vertex. The rightmost geodesic is defined in a similar way.

For two corners c and c ′ and a self-avoiding path Ô from c + to c ′+ in a map m, we may slit the map m along Ô from c to c ′ by doubling each edge of Ô. In the resulting object, there are two copies of the initial path Ô, one lying to the left of Ô and one lying to its right. These are respectively called the left copy and right copy of Ô. See Figure 3.

We say that a half-edge

h is directed toward a vertex v if d m (h + , v) < d m (h -, v), that it is directed away from v if d m (h + , v) > d m (h -, v) and that it is parallel to v if d m (h + , v) = d m (h -, v).
In the following figures and pictographs, we will represent half-edges with half arrowheads and use the shorthand notation v in order to mean directed toward v, and v to mean directed away from v. The leftmost and rightmost geodesics from a half-edge h directed toward a vertex or a corner to the latter is defined with the above procedure, starting with the half-edge h.

We end this section by mentioning the following useful elementary facts on bipartite and quasibipartite plane maps. See the extended version of this paper for a proof.

Proposition 5. The following holds.

(i) In a bipartite map, no edge can be parallel to a vertex. More precisely, for any given face and any given vertex, exactly half of the half-edges incident to the face are directed toward the vertex, the other half being directed away from the vertex. Let p be a path. We denote by p i→j the path (p i , . . . ,

p j ) if 1 ≤ i ≤ j ≤ [p],
or the empty path otherwise. If q is another path satisfying q - 1 = p +

[p] , we set

p • q := (p 1 , . . . , p [p] , q 1 , . . . , q [q] )
the concatenation of p and q. Throughout this paper, the notion of metric we use is the graph metric: if m is a map, the distance d m (v, v ) between two vertices v and v is the smaller for which there exists a path of length from v to v . A geodesic from v to v is such a path. The leftmost geodesic from a corner c to a vertex or to a corner is constructed as follows. First, we consider all the geodesics from c + to the vertex or to the vertex corresponding to the corner. We take the set of all the first steps of these geodesics.

Starting from c, we select the first half-edge to its left that belongs to this set. Then we iterate the process from this half-edge until we reach the desired vertex. The rightmost geodesic is defined in a similar way.

For two corners c and c and a self-avoiding path p from c + to c + in a map m, we may slit the map m along p from c to c by doubling each edge of p. In the resulting object, there are two copies of the initial path p, one lying to the left of p and one lying to its right. These are respectively called the left copy and right copy of p. See Figure 3.

We say that a half-edge h is directed toward

a vertex v if d m (h + , v) < d m (h -, v), that it is directed away from v if d m (h + , v) > d m (h -, v) and that it is parallel to v if d m (h + , v) = d m (h -, v).
In the following figures and pictographs, we will represent half-edges with half arrowheads and use the shorthand notation v in order to mean directed toward v, and v to mean directed away from v. The leftmost and rightmost geodesics from a half-edge h directed toward a vertex or a corner to the latter is defined with the above procedure, starting with the half-edge h.

We end this section by mentioning the following useful elementary facts on bipartite and quasibipartite plane maps. See the extended version of this paper for a proof. (i) In a bipartite map, no edge can be parallel to a vertex. More precisely, for any given face and any given vertex, exactly half of the half-edges incident to the face are directed toward the vertex, the other half being directed away from the vertex.

(ii) In a quasibipartite map, a cycle has odd length if and only if it separates the two odd-degree faces 1 . Moreover, for any given vertex v, among the a half-edges incident to an odd-degree face, exactly one is parallel to v, (a -1)/2 are directed toward v and (a -1)/2 are directed away from v.

Adding two corners to a face in a bipartite map

Throughout this section, we fix an r-tuple a = (a 1 , . . . , a r ) of positive even integers and define ã := (a 1 + 2, a 2 , . . . , a r ) as in the statement of Proposition 1. We consider the set M of plane maps of type a carrying one distinguished edge and two distinguished corners in the first face. On the other hand, we consider the set M of plane maps of type ã carrying one distinguished vertex and two different distinguished half-edges incident to the first face, and that are both directed toward the distinguished vertex.

6

Jérémie Bettinelli

(ii) In a quasibipartite map, a cycle has odd length if and only if it separates the two odd-degree faces 1 . Moreover, for any given vertex v, among the a half-edges incident to an odd-degree face, exactly one is parallel to v, (a -1)/2 are directed toward v and (a -1)/2 are directed away from v.

Adding two corners to a face in a bipartite map

Throughout this section, we fix an r-tuple a = (a 1 , . . . , a r ) of positive even integers and define ã := (a 1 + 2, a 2 , . . . , a r ) as in the statement of Proposition 1. We consider the set M of plane maps of type a carrying one distinguished edge and two distinguished corners in the first face. On the other hand, we consider the set M of plane maps of type ã carrying one distinguished vertex and two different distinguished half-edges incident to the first face, and that are both directed toward the distinguished vertex.

PSfrag replacements

f 1 f 1 +2 v M M c c ′ h v h ′ v e
By Proposition 5.(i), the cardinalities of M and M are the sides of (1.3). We present an explicit bijection between these two sets; this provides a combinatorial interpretation of Proposition 1. Our bijection is a straightforward generalization of [1, Section 4].

Increasing the size. Let (m; e, c, c ′ ) ∈ M. As m is bipartite, e cannot be parallel to c: we denote by e the corresponding half-edge that is directed toward c, and by the rightmost geodesic from e to c. Let us first suppose that rev( e) is directed toward c ′ : in this case, the quadruple (m; e, c, c ′ ) is called simple. We denote by ′ the rightmost geodesic from rev( e) to c ′ and define the self-avoiding path Ô := rev() • rev( e) • ′ . We slit m along Ô from c to c ′ , and we denote by Ð and Ö the left and right copies of Ô in the resulting maps. We then sew back Ð 1→[Ô]-1 onto Ö 2→[Ô] , in the sense that we identify Ð k with Ö k+1 for 1 ≤ k ≤ [Ô] -1. We denote by m the resulting map and let the outcome of the construction be the quadruple ( m; Ð + [] , Ö 1 , rev(Ð) 1 ). See Figure 3. Let us now treat the case where e is directed toward c ′ . We denote by ′ the rightmost geodesic from e to c ′ and by i ≥ 1 the smallest integer such that i = ′ i . As and ′ are By 5.(i), the cardinalities of M and M are the sides of (1.3). We present an explicit bijection between these two sets; this provides a combinatorial interpretation of Proposition 1. Our bijection is a straightforward generalization of [1, Section 4].

Increasing the size. Let (m; e, c, c ) ∈ M. As m is bipartite, e cannot be parallel to c: we denote by e the corresponding half-edge that is directed toward c, and by c the rightmost geodesic from e to c. Let us first suppose that rev( e) is directed toward c : in this case, the quadruple (m; e, c, c ) is called simple. We denote by c the rightmost geodesic from rev( e) to c and define the self-avoiding path p := rev(c) • rev( e) • c . We slit m along p from c to c , and we denote by l and r the left and right copies of p in the resulting maps. We then sew back l 1→[p]-1 onto r 2→[p] , in the sense that we identify l k with r k+1 for 1 ≤ k ≤ [p] -1. We denote by m the resulting map and let the outcome of the construction be the quadruple ( m; l +

[c] , r 1 , rev(l) 1 ). See Figure 3. Let us now treat the case where e is directed toward c . We denote by c the rightmost geodesic from e to c and by i ≥ 1 the smallest integer such that c i = c i . As c and c are

f 1 v Ð Ö m m c c ′ h h ′ e Ô 1 Ô 2 Ô3 Ô 4 Ô5 Ô6 Ô 7 Ô8
Figure 3: The mapping from M to M in the simple case. We define the path Ô, slit it and sew back after slightly sliding. Only the marked corner of f 1 is represented.

rightmost geodesics, we must have

{ + i , . . . , + [] } ∩ { ′+ i , . . . , ′+ [ ′ ] } = ∅. The path Ô := rev() • rev( e) • e • ′ is thus composed of the self-avoiding path rev( i→[] ) • ′ i→[ ′ ]
together with the selfavoiding path e • 1→i-1 (visited twice, first backwards then forward), grafted either to its left or to its right. We say that the path Ô and the quadruple (m; e, c, c ′ ) are left-pinched or right-pinched accordingly.

As above, we slit m along Ô from c to c ′ , circumventing the pinched part. This still splits m into two submaps with a copy of Ô on the boundary of each but, this time, one copy is a self-avoiding path while the other copy goes back and forth along a "dangling" chain of i edges at some point. We still denote the left and right copies of Ô by Ð and Ö and sew back Ð 1→[Ô]-1 onto Ö 2→[Ô] . We denote by m the resulting map and let the outcome of the construction be the quadruple ( m; Ð + [] , Ö 1 , rev(Ð) 1 ) in the left-pinched case and ( m; (rev(Ö)) +

[ ′ ] , Ö 1 , rev(Ð) 1 ) in the right-pinched case (so that the distinguished vertex is always the tip of the dangling chain). See Figure 4 for a similar operation.

Decreasing the size. The inverse mapping takes a quadruple ( m; v, h, h ′ ) ∈ M and goes as follows. We consider the corner h 0 delimited by h and its predecessor in the contour of the first face of m, and denote by the leftmost geodesic from this corner to v. As h is directed toward v, we have that [ ] ≥ 1 and 1 = h. We define h ′ 0 and ′ in a similar fashion with h ′ instead of h. Depending on whether and ′ meet before reaching v or not, the path Ô ′ := • rev( ′ ) is either self-avoiding or pinched in the sense of the previous paragraph. The quadruple ( m; v, h, h ′ ) is called simple, left-pinched or right-pinched accordingly. We slit m along Ô ′ from h 0 to h ′ 0 , denote by Ð ′ and Ö ′ the left and right copies of Ô ′ in the resulting maps and sew Ð ′

2→[Ô ′ ] onto Ö ′ 1→[Ô ′ ]-1 .
In the resulting map, Ð ′ 1 and (rev(Ö ′ )) 1 are dangling edges. We suppress them and denote respectively by c and c ′ the corners they define. We denote by m the map we finally obtain and let the outcome of the construction be the quadruple (m; e, c, c ′ ), where e is the edge corresponding to Ð ′ [ ]+1 . As above, we slit m along p from c to c , circumventing the pinched part. This still splits m into two submaps with a copy of p on the boundary of each but, this time, one copy is a self-avoiding path while the other copy goes back and forth along a "dangling" chain of i edges at some point. We still denote the left and right copies of p by l and r and sew back l 1→[p]-1 onto r 2→ [p] . We denote by m the resulting map and let the outcome of the construction be the quadruple ( m; l +

[c] , r 1 , rev(l) 1 ) in the left-pinched case and ( m; (rev(r)) +

[c ] , r 1 , rev(l) 1 ) in the right-pinched case (so that the distinguished vertex is always the tip of the dangling chain). See Figure 4 for a similar operation.

Decreasing the size. The inverse mapping takes a quadruple ( m; v, h, h ) ∈ M and goes as follows. We consider the corner h 0 delimited by h and its predecessor in the contour of the first face of m, and denote by h the leftmost geodesic from this corner to v. As h is directed toward v, we have that [h] ≥ 1 and h 1 = h. We define h 0 and h in a similar fashion with h instead of h. Depending on whether h and h meet before reaching v or not, the path p := h • rev(h ) is either self-avoiding or pinched in the sense of the previous paragraph. The quadruple ( m; v, h, h ) is called simple, left-pinched or right-pinched accordingly. We slit m along p from h 0 to h 0 , denote by l and r the left and right copies of p in the resulting maps and sew l 2→[p ] onto r 1→[p ]-1 . In the resulting map, l 1 and (rev(r )) 1 are dangling edges. We suppress them and denote respectively by c and c the corners they define. We denote by m the map we finally obtain and let the outcome of the construction be the quadruple (m; e, c, c ), where e is the edge corresponding to l [h]+1 .

The previous mappings are inverse one from another. In fact, through the mappings of the two previous paragraphs, simple quadruples correspond to simple quadruples, left-pinched quadruples correspond to left-pinched quadruples and right-pinched quadruples correspond to right-pinched quadruples.

The proof that the previous mappings are inverse one from another can be copied almost verbatim from [1, Proof of Theorem 3]. Alternatively, we will see in Section 5.3 that these mappings can be seen as compositions of simpler slit-slide-sew bijections; this will provide an alternate, arguably simpler, proof.

Adding one corner to two faces in a bipartite map

We now fix an r-tuple a = (a 1 , . . . , a r ) of positive even integers and we define ã := (a 1 + 1, a 2 + 1, a 3 , . . . , a r ). We let M be the set of plane maps of type a carrying one distinguished edge, one distinguished corner in the first face and one distinguished corner in the second face. We let M be the set of plane maps of type ã carrying one distinguished vertex and two distinguished half-edges directed toward it, one being incident to the first face and one being incident to the second face.

8

Jérémie Bettinelli

The previous mappings are inverse one from another. In fact, through the mappings of the two previous paragraphs, simple quadruples correspond to simple quadruples, left-pinched quadruples correspond to left-pinched quadruples and right-pinched quadruples correspond to right-pinched quadruples.

The proof that the previous mappings are inverse one from another can be copied almost verbatim from [1, Proof of Theorem 3]. Alternatively, we will see in Section 5.3 that these mappings can be seen as compositions of simpler slit-slide-sew bijections; this will provide an alternate, arguably simpler, proof.

Adding one corner to two faces in a bipartite map

We now fix an r-tuple a = (a 1 , . . . , a r ) of positive even integers and we define ã := (a 1 + 1, a 2 + 1, a 3 , . . . , a r ). We let M be the set of plane maps of type a carrying one distinguished edge, one distinguished corner in the first face and one distinguished corner in the second face. We let M be the set of plane maps of type ã carrying one distinguished vertex and two distinguished half-edges directed toward it, one being incident to the first face and one being incident to the second face.

PSfrag replacements

f 1 f 1 f 2 f 2 +1 +1 v M M c c ′ h v h ′ v e
The cardinality of M is clearly equal to the left-hand side of (1.4) and we see that the cardinality of M is equal to the right-hand side of (1.4) by using Proposition 5.(ii). The mappings interpreting Proposition 2 are described exactly as in the previous section: see Figure 4. The only difference is that the paths Ô and Ô ′ no longer disconnect the maps; this bears no effects in the description of the mappings.

It is not very hard to see that the paths Ô and Ô ′ are as before (self-avoiding or pinched); we refer the reader to the extended version.

Transfer bijections

Transferring from a face of degree at least two

We start with the setting of Proposition 3. We let M be the set of plane maps of type a carrying one distinguished corner c in the first face and one distinguished half-edge h ′

The cardinality of M is clearly equal to the left-hand side of (1.4) and we see that the cardinality of M is equal to the right-hand side of (1.4) by using Proposition 5.(ii). The mappings interpreting Proposition 2 are described exactly as in the previous section: see Figure 4. The only difference is that the paths p and p no longer disconnect the maps; this bears no effects in the description of the mappings.

It is not very hard to see that the paths p and p are as before (self-avoiding or pinched); we refer the reader to the extended version.

Transfer bijections

Transferring from a face of degree at least two

We start with the setting of Proposition 3. We let M be the set of plane maps of type a carrying one distinguished corner c in the first face and one distinguished half-edge h g replacements

f 1 f 1 f 2 f 2 v Ð Ö m m c c ′ h h ′ e Figure 4:
The mapping from M to M in the pinched case.

incident to the r + 1-th face and directed toward c. We define M as the set of plane maps of type ã carrying one distinguished corner c ′ in f r+1 and one distinguished half-edge h incident to the first face and directed away from c ′ .

PSfrag replacements

f 1 f 1 f r+1 f r+1 +1 -1 M M c c ′ h c ′ h ′ c
Let us describe the mappings (see the left part of Figure 5) between M and M. Let (m; c, h ′ ) ∈ M. We consider the corner h ′ 0 delimited by h ′ and its predecessor in the contour of f r+1 , and denote by ′ the leftmost geodesic from h ′ 0 to c. We slit m along ′ from h ′ 0 to c, denote by Ð ′ and Ö ′ the left and right copies of ′ in the resulting map and sew Ð

′ 2→[ ′ ] onto Ö ′ 1→[ ′ ]-1 .
In the resulting map, we denote by h the half-edge Ö ′

[ ′ ] ,
suppress the dangling edge Ð ′ 1 and denote by c ′ the corner it defines. We then denote by m the resulting map and let the outcome of the construction be

Φ left (m; c, h ′ ) := ( m; c ′ , h).
Conversely, starting from ( m; c ′ , h) ∈ M, we consider the corner h 0 delimited by h and its successor in the contour of f 1 , and denote by the rightmost geodesic from h 0 to c ′ . We slit m along from h 0 to c ′ , denote by Ð and Ö the left and right copies of in the resulting map and sew Ð 1→[ ]-1 onto Ö 2→[ ] . In the resulting map, we denote by h ′ the half-edge rev(Ð) 1 , suppress the dangling edge Ö 1 and denote by c the corner it defines. We then denote by m the resulting map and let the outcome of the construction be Φ right ( m; c ′ , h) := (m; c, h ′ ). Theorem 6. The mappings Φ left : M → M and Φ right : M → M are inverse bijections.

We refer the reader to the extended version for the proof. incident to the r + 1-th face and directed toward c. We define M as the set of plane maps of type ã carrying one distinguished corner c in f r+1 and one distinguished half-edge h incident to the first face and directed away from c .

Slit-slide-sew bijections for bipartite and quasibipartite plane maps 9

g replacements

f 1 f 1 f 2 f 2 v Ð Ö m m c c ′ h h ′ e Figure 4:
The mapping from M to M in the pinched case.

incident to the r + 1-th face and directed toward c. We define M as the set of plane maps of type ã carrying one distinguished corner c ′ in f r+1 and one distinguished half-edge h incident to the first face and directed away from c ′ .

PSfrag replacements

f 1 f 1 f r+1 f r+1 +1 -1 M M c c ′ h c ′ h ′ c
Let us describe the mappings (see the left part of Figure 5) between M and M. Let (m; c, h ′ ) ∈ M. We consider the corner h ′ 0 delimited by h ′ and its predecessor in the contour of f r+1 , and denote by ′ the leftmost geodesic from h ′ 0 to c. We slit m along ′ from h ′ 0 to c, denote by Ð ′ and Ö ′ the left and right copies of ′ in the resulting map and sew Ð

′ 2→[ ′ ] onto Ö ′ 1→[ ′ ]-1 .
In the resulting map, we denote by h the half-edge Ö ′

[ ′ ] ,

suppress the dangling edge Ð ′ 1 and denote by c ′ the corner it defines. We then denote by m the resulting map and let the outcome of the construction be Φ left (m; c, h ′ ) := ( m; c ′ , h).

Conversely, starting from ( m; c ′ , h) ∈ M, we consider the corner h 0 delimited by h and its successor in the contour of f 1 , and denote by the rightmost geodesic from h 0 to c ′ . We slit m along from h 0 to c ′ , denote by Ð and Ö the left and right copies of in the resulting map and sew Ð 1→[ ]-1 onto Ö 2→[ ] . In the resulting map, we denote by h ′ the half-edge rev(Ð) 1 , suppress the dangling edge Ö 1 and denote by c the corner it defines. We then denote by m the resulting map and let the outcome of the construction be Φ right ( m; c ′ , h) := (m; c, h ′ ). We refer the reader to the extended version for the proof.

Let us describe the mappings (see the left part of Figure 5) between M and M. Let (m; c, h ) ∈ M. We consider the corner h 0 delimited by h and its predecessor in the contour of f r+1 , and denote by h the leftmost geodesic from h 0 to c. We slit m along h from h 0 to c, denote by l and r the left and right copies of h in the resulting map and sew l 2→[h ] onto r 1→[h ]-1 . In the resulting map, we denote by h the half-edge r [h ] , suppress the dangling edge l 1 and denote by c the corner it defines. We then denote by m the resulting map and let the outcome of the construction be Φ left (m; c, h ) := ( m; c , h).

Conversely, starting from ( m; c , h) ∈ M, we consider the corner h 0 delimited by h and its successor in the contour of f 1 , and denote by h the rightmost geodesic from h 0 to c . We slit m along h from h 0 to c , denote by l and r the left and right copies of h in the resulting map and sew l 1→[h]-1 onto r 2→[h] . In the resulting map, we denote by h the half-edge rev(l) 1 , suppress the dangling edge r 1 and denote by c the corner it defines. We then denote by m the resulting map and let the outcome of the construction be Φ right ( m; c , h) := (m; c, h ). Theorem 6. The mappings Φ left : M → M and Φ right : M → M are inverse bijections.

We refer the reader to the extended version for the proof. ag replacements

f 1 f 1 f r+1 f r+1 ′ Ð ′ Ö ′ m m c c ′ h h ′ h ′ 0 PSfrag replacements f 1 f r+1 ′ Ð ′ Ö ′ m m c c ′ h h ′ h ′ 0 f 1 f 1 f r+1 Ô ′ Ð ′ Ö ′ m m c h h 0 v Figure 5:
The transfer mappings from a face of degree more than 2 (left) or 1 (right).

Transferring from a face of degree one

We now turn to the setting of Proposition 4. We let M be the set of plane maps of type a carrying one distinguished corner in the first face and we let M be the set of plane maps of type ã carrying one distinguished vertex and one distinguished half-edge incident to the first face and directed toward the distinguished vertex.

PSfrag replacements

f 1 f 1 f r+1 +1 v M M c h v
The mappings are very similar as above; see the right part of Figure 5. Let (m; c) ∈ M. We slit m along the rightmost geodesic Ô from the unique corner of f r+1 to c. We denote 10 Jérémie Bettinelli ag replacements

f 1 f 1 f r+1 f r+1 ′ Ð ′ Ö ′ m m c c ′ h h ′ h ′ 0 PSfrag replacements f 1 f r+1 ′ Ð ′ Ö ′ m m c c ′ h h ′ h ′ 0 f 1 f 1 f r+1 Ô ′ Ð ′ Ö ′ m m c h h 0 v Figure 5:
The transfer mappings from a face of degree more than 2 (left) or 1 (right).

Transferring from a face of degree one

We now turn to the setting of Proposition 4. We let M be the set of plane maps of type a carrying one distinguished corner in the first face and we let M be the set of plane maps of type ã carrying one distinguished vertex and one distinguished half-edge incident to the first face and directed toward the distinguished vertex.

PSfrag replacements

f 1 f 1 f r+1 +1 v M M c h v
The mappings are very similar as above; see the right part of Figure 5. Let (m; c) ∈ M. We slit m along the rightmost geodesic Ô from the unique corner of f r+1 to c. We denote

Transferring from a face of degree one

We now turn to the setting of Proposition 4. We let M be the set of plane maps of type a carrying one distinguished corner in the first face and we let M be the set of plane maps of type ã carrying one distinguished vertex and one distinguished half-edge incident to the first face and directed toward the distinguished vertex.

10

Jérémie Bettinelli ag replacements

f 1 f 1 f r+1 f r+1 ′ Ð ′ Ö ′ m m c c ′ h h ′ h ′ 0 PSfrag replacements f 1 f r+1 ′ Ð ′ Ö ′ m m c c ′ h h ′ h ′ 0 f 1 f 1 f r+1 Ô ′ Ð ′ Ö ′ m m c h h 0 v Figure 5:
The transfer mappings from a face of degree more than 2 (left) or 1 (right).

Transferring from a face of degree one

We now turn to the setting of Proposition 4. We let M be the set of plane maps of type a carrying one distinguished corner in the first face and we let M be the set of plane maps of type ã carrying one distinguished vertex and one distinguished half-edge incident to the first face and directed toward the distinguished vertex.

PSfrag replacements

f 1 f 1 f r+1 +1 v M M c h v
The mappings are very similar as above; see the right part of Figure 5. Let (m; c) ∈ M. We slit m along the rightmost geodesic Ô from the unique corner of f r+1 to c. We denote

The mappings are very similar as above; see the right part of Figure 5. Let (m; c) ∈ M.

We slit m along the rightmost geodesic p from the unique corner of f r+1 to c. We denote by l and r the left and right copies of p in the resulting map and define r 0 as the unique half-edge incident to f r+1 . We then sew l 1→[p] onto r 0→[p]-1 , suppressing f r+1 in the process. In the resulting map, we denote by h the half-edge rev(r) 1 and denote by v the vertex l - 1 . We then denote by m the resulting map and let the outcome of the construction be Φ 1 right (m; c) := ( m; v, h). Conversely, starting from ( m; v, h) ∈ M, we consider the corner h 0 delimited by h and its predecessor in the contour of f 1 , and denote by p the leftmost geodesic from h 0 to v. We slit m along p starting from h 0 and stopping at v, without disconnecting the map at v. We denote by l and r the left and right copies of p in the resulting map and sew l 2→[p ] onto r 1→[p ]-1 , thus creating a new degree 1-face, which we denote by f r+1 . In the resulting map, we suppress the dangling edge l 1 and denote by c the corner it defines. We then denote by m the resulting map and let the outcome of the construction be Φ 1 left ( m; v, h) := (m; c).

Theorem 7. The mappings Φ 1 right : M → M and Φ 1 left : M → M are inverse bijections.

Decomposition of growing bijections into transfer bijections

Let us explain our claim that growing bijections are compositions of two transfer bijections. We fix an r-tuple a = (a 1 , . . . , a r ) of positive even integers and consider a map m of type a with a distinguished edge e and two distinguished corners c and c (either of the same face or of two different faces). We first define the map m of type (a 1 , . . . , a r , 2) by replacing the distinguished edge e with an r + 1-th face f r+1 of degree 2 by doubling the edge; the marked corner of this face is arbitrarily chosen. Next, we let h be the unique half-edge incident to f r+1 that is directed away from c. We set (m ; c , h) := Φ right (m ; c, h ) and keep track of c in the resulting map. The map m is of type (a 1 + 1, a 2 , . . . , a r , 1) and we finally set ( m; v, h ) := Φ 1 right (m ; c ), while keeping track of h in the resulting map. See Figure 6.

We claim that ( m; v, h, h ) is the output of the growing bijection of Section 3 or 4. In m, the growing bijection uses two geodesics, one directed toward c and one directed toward c . Plainly, in the application of Φ right to (m ; c, h ), the sliding path in m corresponds to the geodesic directed toward c. To show the claim, we only need to check that the image in m of the geodesic directed toward c corresponds to the sliding path used by Φ 1 right . This is because the mapping Φ right only alters the map along the geodesic directed toward c, which, by definition, cannot cross the geodesic directed toward c .

(either of the same face or of two different faces). We first define the map m of type (a 1 , . . . , a r , 2) by replacing the distinguished edge e with an r + 1-th face f r+1 of degree 2 by doubling the edge; the marked corner of this face is arbitrarily chosen. Next, we let h ′′ be the unique half-edge incident to f r+1 that is directed away from c. We set (m ′′ ; c ′′ , h) := Φ right (m ′ ; c, h ′′ ) and keep track of c ′ in the resulting map. The map m ′′ is of type (a 1 + 1, a 2 , . . . , a r , 1) and we finally set ( m; v, h ′ ) := Φ 1 right (m ′′ ; c ′ ), while keeping track of h in the resulting map. See Figure 6.

PSfrag replacements

m m ′ m ′′ m c c c ′ c ′ c ′ c ′ h h h h ′ e v h ′′

Figure 1 :

 1 Figure 1: A quasibipartite map of type (20, 4, 8, 4, 4, 3, 4, 4, 4, 6, 4, 7, 4, 2).

Figure 1 :

 1 Figure 1: A quasibipartite map of type (20, 4, 8, 4, 4, 3, 4, 4, 4, 6, 4, 7, 4, 2).

Figure 2 :

 2 Figure 2: The two different ways of distinguishing twice the same corner.

Figure 2 :

 2 Figure 2: The two different ways of distinguishing twice the same corner.

Proposition 5 .

 5 The following holds.

Figure 3 :

 3 Figure 3:The mapping from M to M in the simple case. We define the path p, slit it and sew back after slightly sliding. Only the marked corner of f 1 is represented.

Figure 4 :

 4 Figure 4: The mapping from M to M in the pinched case.

Theorem 6 .

 6 The mappings Φ left : M → M and Φ right : M → M are inverse bijections.

Figure 5 :

 5 Figure 5: The transfer mappings from a face of degree more than 2 (left) or 1 (right).

Figure 6 :

 6 Figure 6: Two-step decomposition of a growing bijection into transfer bijections. To be read from top to bottom.Figure 6: Two-step decomposition of a growing bijection into transfer bijections. To be read from top to bottom.

Figure 6 :

 6 Figure 6: Two-step decomposition of a growing bijection into transfer bijections. To be read from top to bottom.Figure 6: Two-step decomposition of a growing bijection into transfer bijections. To be read from top to bottom.

Recall that, by the Jordan Curve Theorem, a cycle in a plane map always separates the map into exactly two connected components.

Slit-slide-sew bijections for bipartite and quasibipartite plane maps

Jérémie Bettinelli

Acknowledgements

We thank Olivier Bernardi and Éric Fusy for interesting discussions on this topic.

This work is partially supported by Grant ANR-14-CE25-0014.