text:
\subsubsection{\@ucheadfalse
  \@startsection{subsubsection}{3}{\z@}{6pt plus
    1pt}{-8pt}{\reset@font\normalsize\sffamily}}
\makeatother
\def\subsubsection*{\subsubsection*}

\newcommand{\mathfrak{m}}{\mathfrak{m}}
\newcommand{\mathfrak{q}}{\mathfrak{q}}
\newcommand{\mathfrak{p}}{\mathfrak{p}}
\newcommand{\mathfrak{t}}{\mathfrak{t}}
\newcommand{\mathfrak{e}}{\mathfrak{e}}
\newcommand{\mathfrak{p}}{\mathfrak{p}}
\newcommand{\mathfrak{s}}{\mathfrak{s}}
\newcommand{\mathfrak{r}}{\mathfrak{r}}

\firstfoot{}
\runningfoot{}
\markboth{}{}

\author{Guillaume Chapuy, LIX, \'Ecole Polytechnique
  \and Michel Marcus, LaBRI, Universit\'e Bordeaux 1
  \and Gilles Schaeffer, LIX, CNRS and \'Ecole Polytechnique}
\title{A bijection for rooted maps on orientable surfaces}

\begin{abstract}
The enumeration of maps and the study of uniform random maps have been
classical topics of combinatorics and statistical physics ever since
the seminal work of Tutte in the sixties.  Following the bijective
approach initiated by Cori and Vauquelin in the eighties, we describe
a bijection between rooted maps, or rooted bipartite quadrangulations,
on a surface of genus $g$ and some simpler objects that generalize
plane trees.
Thanks to a rerooting argument, our bijection allows to compute the
generating series of rooted maps on a surface of genus $g$ with
respect to the number of edges, and to recover the asymptotic numbers
of such maps.

Our construction allows to keep track in a bipartite quadrangulation
of the distances of all vertices to a random basepoint. This is an
analog for higher genus surfaces of the basic result on which were
built the recent advances in the comprehension of the intrinsec
geometry of large random planar maps, hopefully opening the way to the
study of a model of continuum random surfaces of genus $g$.
\end{abstract}

\category{Combinatorics}{G.2.1}{Enumeration; Graph theory}
\keywords{Graphs on surfaces, trees, random discrete surfaces}

\date{{between 14 Oct 1998 and december 2007}}

\begin{document}

\begin{bottomstuff}
 {G.S. acknowledges financial support from the french ministery of
   research via grants ACI-MD Geocomp and ANR Sada.}
\end{bottomstuff}
\maketitle

\section{Introduction}
\label{sec:in}

This article is concerned with the enumerative and probabilistic study
of \emph{maps on orientable surfaces}: rougly speaking a map of genus
$g$ is a proper embedding of a graph in $\mathcal{S}_g$, the compact
oriented surface of genus $g$ without boundary.  Maps on the sphere
$\mathcal{S}_0$, also known as \emph{planar maps}, have been studied
in enumerative combinatorics ever since the seminal papers of William
T. Tutte in the sixties \cite{Tutte:census}, and our primary
motivation is still to explore the unexpected enumerative properties
of these objects: For instance, the number of rooted planar maps
having $n$ edges is given by the simple formula
\begin{equation}\label{planar}
\vec{q}_{0,n}=\frac{2\cdot 3^n(2n)!}{(n+2)!\,n!},
\end{equation}
and the number of rooted maps of genus $g$ having
$n$ edges satisfies
\begin{equation}\label{genusg}
\vec{q}_{g,n}\sim  c_g\cdot n^{\frac52(g-1)}\cdot12^n,
\end{equation}
when $n$ goes to infinity with $g$ fixed.  The remarkable linear
dependency in $g$ of the polynomial growth exponent of this asymptotic
formula has been observed as a common pattern of many classes of maps
in combinatorics \cite{BeCa,Gao}. Formula~(\ref{planar}) for the
planar case was recovered also in the physics literature by mean of
the so-called genus expansions of matrix integrals \cite{BIPZ}, which
also led in the 90's to independant derivations of the asymptotic
formula~(\ref{genusg}) \cite[and reference therein]{DFGiZJ}.  Until
now however it has remained an open problem to give a combinatorial
explanation of the linear dependency in the genus \cite{Be:overview}.

The aim of this paper is to describe a bijection
(Theorem~\ref{thm:bijection}) which reformulates and extends to higher
genus surfaces an earlier bijection of Cori and Vauquelin \cite{CoVa}
between planar maps and well labelled trees. In the planar case, a
rerooting argument then immediately leads to Formula~\ref{planar}
(Corollary~\ref{cor:planar}). In higher genus, the combination of our
bijection with a decomposition inspired from Wright's works on labeled
graphs with fixed excess \cite{Wr77,Wr78} leads to a simple combinatorial
derivation of Formula~(\ref{genusg}) (Corollary~\ref{cor:genusg}), and
to a new expression of the generating series for maps of genus $g$
with respect to the number of edges
(Theorem~\ref{thm:genusg}). Classical results of singularity analysis
allow then to recover easily the asymptotic formula~(\ref{genusg}), and
provides a new expression to the constant $c_g$ in front of the formula
(Corollary~\ref{cor:genusg}).

One motivation for the study of maps in statistical physics is the
interpretation of random maps as discrete models of surfaces in the
context of two-dimensional euclidean quantum gravity
\cite{AmDuJo97}.  From a probabilistic point of view, it is
natural to wonder about the geometry of these random discrete
surfaces.  In the planar case our bijection was already used in
\cite{ChSc04} to show that the distance between two random vertices in
a uniform random planar quadrangulation with $n$ faces is of order
$n^{1/4}$, and more generally to study the process describing the
number of vertices at distance $k$ of a vertex.  This line of research
has lead to remarkable progress in our understanding of the geometry
of large random planar maps \cite{BDFG} and of their continuum limit
\cite{MaMo,LG,LGPa}. From this perspective we provide here the basic
building block for the study of higher genus random discrete surfaces.

\section{Maps, quadrangulations and $g$-trees}
In this section we make precise our use of the graph terminology.

\subsection{Graph drawings and maps}
\begin{figure}
\centerline{\includegraphics[scale=.5]{fig1}}
\caption{A rooted planar map, a graph drawing on $\mathcal{S}_1$ and a
map of genus $1$. }
\end{figure}
Let $\mathcal S_g$ denote the compact oriented surface of genus $g$
without boundary.  A \emph{graph drawing} on $\mathcal{S}_g$ is a proper
embedding (without edge crossings) of a graph into $\mathcal{S}_g$.
Multiple edges and loops are allowed. A graph drawing on
$\mathcal{S}_g$ is a \emph{map of genus $g$} if moreover each face is
homeomorphic to a disc, or equivalently, if the complement of the
graph in $S_g$ is a union of disjoint simply connected components. In
particular the graph underlying a map is necessarily connected.  Maps
of genus 0 are called \emph{planar maps}.
For enumerative purpose it is convenient to consider \emph{rooted
maps}, that is, pairs $\vec \mathfrak{m}=(\mathfrak{m},e)$ where $\vec e$ is an arc of
$\mathfrak{m}$ (an arc is an edge with an orientation). The arc $\vec e$ is
called the \emph{root} of $\vec \mathfrak{m}$, its origin is the \emph{root
vertex} of $\mathfrak{m}$ and the face on its right is the \emph{root face}.

In the rest of this text, two maps are considered the same if there
exists an orientation preserving homeomorphism of the embedding
surface that sends one map onto the other (carrying roots if there are
some). These (equivalence classes of) maps can also be defined in a
purely combinatorial way: for instance a rooted map can be described
by listing the local arrangement of arcs around each vertex using any
numbering of these arcs. A modern account of the equivalence between
topological and combinatorial descriptions of maps can be found in
\cite[Ch.~3]{MoTo}.

To any rooted map $\vec\mathfrak{m}$ we associate an arbitrary fixed numbering
of its edges (respectively arcs, vertices, corners, or faces) that
starts with the root edge, which we call the \emph{canonical order} of
the edges (respectively arcs, vertices, corners, or faces) of
$\vec\mathfrak{m}$. This numbering can for instance be given by the first visit
in a depth first search turning counterclockwise around each vertex, or
by any other fixed procedure: in what follows we will only need to
invoke this canonical order to fix notations.

A fundamental result of the theory of surfaces is the Euler
characteristic formula:
\begin{lemma}\label{lem:euler}
If a map of genus $g$ has $v$ vertices, $f$ faces and $n$ edges then
\[
v-n+f=2-2g.
\]
\end{lemma}
The quantity $\chi=2-2g$ is called the Euler characteristic of the map.

\subsection{Maps and bipartite quadrangulations}
The \emph{degree of a vertex} is the number of edges incident to it,
with the convention that a loop counts for two. The \emph{degree of a
face} is the number of edges incident to it, with the convention that
an edge incident to the same face on both sides counts for two.
\begin{figure}
\centerline{\includegraphics[scale=.5]{fig2}}
\caption{The quadrangulation of a map: local construction and an exemple
in the plane}
\end{figure}
A \emph{quadrangulation} is a planar map having all faces of degree
4. A map is \emph{bipartite} if its vertices are colored in two colors
in such a way that adjacent vertices have different colors (say black
and white). By convention the color of the root vertex of a rooted
bipartite map is always taken to be black.  We recall two standard
results of graph and map theory:
\begin{enumerate}
\item All planar quadrangulations admit a bipartition.
\item For all $n,v,f\geq1$ and $g\geq0$ with $v-n+f=2-2g$, there is a
bijection between maps of genus $g$ with $n$ edges, $v$ vertices and
$f$ faces, and bipartite quadrangulations of genus $g$ with $n$ faces,
$v$ black and $f$ white vertices, and $2n$ edges. Idem between rooted
maps and rooted bipartite quadrangulations.
\end{enumerate}
The first result will not be used but is recalled to stress the fact
that, \emph{a contrario}, a similar statement does not hold for
quadrangulations of genus $g$: there exist non bipartite
quadrangulations of genus $g$ for all $g\geq 1$.

The second result is based on a classical construction which we now
briefly recall: Given a map $\mathfrak{m}$ with black vertices, triangulate
each face from a new white vertex; the new bipartite edges form with
black and white vertices a quadrangulation $\mathfrak{q}$, which is the
bipartite quadrangulation associated to $\mathfrak{m}$. Conversely given a
bipartite quadrangulation $\mathfrak{q}$ create inside each face $f$ a new edge
connecting the two black vertices incident to $f$; these new edges
form with the black vertices a map $\mathfrak{m}$ whose bipartite
quadrangulation is $\mathfrak{q}$.  To get a correspondence in the rooted case,
a rerooting convention must be chosen: if $\mathfrak{m}$ has a root edge $e$,
then let the root of $\mathfrak{q}$ be the arc of $\mathfrak{q}$ with origin the origin
of $e$ and with the face containing $e$ on its right hand side.  This
correspondence is the reason why, although we concentrate in the rest
of this text on bipartite quadrangulations, our results have
implications for all maps.

\subsection{Quadrangulations, distance labelling and $g$-trees}
A \emph{pointed} quadrangulation is a pair $\mathfrak{q}^\bullet=(\mathfrak{q},v_0)$,
where $v_0$ is a vertex of $\mathfrak{q}$, called the \emph{basepoint}. The
\emph{distance labelling} of $(\mathfrak{q},v_0)$ is a labelling of the
vertices of $\mathfrak{q}$ by their distance to $v_0$ in the underlying graph:
the label of a vertex $v$ is the minimum number of edges of a path
returning from $v$ to $v_0$.  Observe that in a pointed bipartite
quadrangulation the vertices with the same color as the basepoint are
exactly the vertices at even distance of it. In particular two
adjacent vertices have labels that differ by one in the distance
labelling, and the faces are of two types depending whether the cycle
of incident labels is of the form $(i-1,i,i-1,i)$ or $(i-1,i,i+1)$
for some $i\geq1$.

\begin{figure}
\centerline{\includegraphics[scale=.4]{Quad-bip}}
\caption{A quadrangulation and its distance labeling}
\end{figure}

A \emph{plane tree} is a planar map with only one face. In particular
a planar tree contains no simple cycle of edges, and the definition of
rooted planar trees agrees with the usual recursive combinatorial
definition of ordered trees: a rooted plane tree can be uniquely
decomposed into a root vertex and a (possibly empty) ordered sequence
of rooted planar trees.  By extension, we call \emph{$g$-tree} a map
of genus $g$ with one face. Observe however that for $g\geq1$, any
$g$-tree contains simple cycles of edges.

\section{Embedded $g$-trees and the opening bijection}
A map is called \emph{embedded} if its vertices are given integer
labels that differ at most by one along every edge, the root vertex
(if the map is rooted) having label 1. A map is \emph{well labeled} if
moreover the support of labels is an interval of the form $(1,m)$. In
other terms a well labeled map is an embedded map with minimum label
$1$.

\subsection{The opening of a pointed bipartite quadrangulation}
Given a pointed bipartite quadrangulation $(\mathfrak{q},v_0)$ of genus $g$
having $n$ faces, we define a mapping $\phi$, the \emph{opening},
which we will later claim produces a well labeled $g$-tree with $n$
edges (see Figure~\ref{fig:rules}):
\begin{itemize}
\item Label vertices of $\mathfrak{q}$ according to their distance to
$v_0$. Recall that the extremities of each edge have labels that
differ by one, so that the labels of vertices on the border of a face
form either a cycle $(i-1,i,i-1,i)$ or a cycle $(i-1,i,i+1,i)$.
\item Create a graph drawing $\phi(\mathfrak{q},v_0)$ on $\mathcal{S}_g$ with
vertex set the vertices of $\mathfrak{q}$ except $v_0$ and with one edge $e_f$
for each face $f$ of $\mathfrak{q}$, which connects the two corners of $f$ that
have a vertex label larger than their predecessor in clockwise
direction around $f$: in a face with border $(i-1,i,i-1,i)$ the
resulting edge has label $(i,i)$, while in a face with border
$(i-1,i,i+1,i)$ it has label $(i,i+1)$.
\end{itemize}
\begin{figure}
\centerline{\includegraphics[scale=.48]{Rules}}
\caption{The mapping $\phi$: local rules and an example}\label{fig:rules}
\end{figure}

Obviously the labels of the vertices of $\phi(\mathfrak{q},v_0)$ are positive
and the variations along its edges belong to $\{+1,0,-1\}$, so that
$\phi(\mathfrak{q},v_0)$ is well labelled. More interesting is the following
lemma, which proves that $\phi(\mathfrak{q},v_0)$ is a well labelled $g$-tree.
\begin{lemma}\label{lem:open}
The graph drawing $\phi(\mathfrak{q},v_0)$ on $\mathcal{S}_g$ has a unique and
simply connected face.
\end{lemma}
\begin{proof} We give here a quick proof which requires some
familiarity with graph on surfaces, and postpone a more explicit proof
to the appendix. The graph drawing $\mathfrak{q}'=\mathfrak{q}\cup\phi(\mathfrak{q},v_0)$ is
obviously a map: each face of $\mathfrak{q}$ is divided in $\mathfrak{q}'$ into 2
smaller simply connected faces by an edge of $\phi(\mathfrak{q},v_0)$ (see
Figure~\ref{fig:rules}). Draw a fake vertex $v_f$ in each face $f$ of
$\mathfrak{q}'$, label it by the smallest label on the border of $f$, and
connect these fake vertices by one fake edge for each edge of $\mathfrak{q}$:
an edge $e$ of $\mathfrak{q}$ with label $(i,i+1)$ that separates faces $f$ (on
its right hand side)

\begin{figure}
\centerline{\includegraphics[scale=.7]{PreuveDualeBis}}
\caption{The orientation of dual old edges in $\mathfrak{q}'$: local
configurations and an example.}\label{fig:preuveduale}
\end{figure}

Let us prove that the fake edges form a forest of oriented trees
attached to a unique oriented cycle around $v_0$. Consider the 3 types
of faces of $\mathfrak{q}'$ as represented on Figure~\ref{fig:preuveduale}:
There is exactly one outgoing fake edge in each face, that is, from
each fake vertex, and all oriented fake edges are weakly
decreasing. Hence an oriented cycle of fake edges connects fake
vertices with equal labels. But such a cycle turns counterclockwise
around a unique vertex $v$ of $\mathfrak{q}$, which must be $v_0$ since all its
neighbors have larger labels.

To conclude the proof of the lemma, observe that there can be only one
face in $\phi(\mathfrak{q},v_0)$ since the fake edges connect all faces of
$\mathfrak{q}'$, and that any loop in this face can be retracted along the tree
like structure of fake edges.
\end{proof}

\subsection{Well labelled polygons, chords diagrams,
and the closure of a well labelled $g$-tree} We now describe a mapping
$\psi$ which we later claim to be the inverse of $\phi$.  The
construction of $\psi(\mathfrak{t})$ will take place in the unique face of
$\mathfrak{t}$, which is homeomorphic to a disk by definition of maps: in
particular the actual genus of $S_g$ will be somewhat irrelevant for
this reverse construction, which will reveal to be a simple adaptation
of the construction used in \cite{Sc:PhD,ChSc04,MaMo} for the planar
($g=0$) case. More precisely, given a labelled $g$-tree $\mathfrak{t}$ with
$n$ edges, we decompose it into a rooted $g$-tree $\vec\mathfrak{t}_0$
(forgetting the labels) and a well labelled rooted $2n$-gon $\vec\mathfrak{p}$
(describing the sequence of labels along the border of the unique face
of $\mathfrak{t}$).

We will use the following folklore combinatorial result:
\begin{lemma}\label{lem:luka}
Let $\vec\mathfrak{p}$ be a rooted labelled $m$-gon with labels $a_1,\ldots,a_{m}$
in clockwise order starting after the root edge, and assume that the
labels satisfy the \emph{Lukasiewicz} condition $a_{i+1}-a_i\geq -1$,
and $a_i>a_m$ for all $i$.

Let $\pi:\{1,\ldots,m-1\}\to\{2,\ldots,m\}$ be the application that
maps $i$ to its \emph{predecessor}, that is the smallest $j>i$ such
that $a_j=a_i-1$.

Then there exists a unique way to draw all the edges $(i,\pi(i))$
inside $\vec\mathfrak{p}$ so that the resulting graph drawing is a planar map.  In
this map, each inner face is incident exactly once to the polygon,
along an edge $(a_i,a_{i+1})$, and the labels on the border of this
face are then, in clockwise direction,
$(a_i,a_{i+1},a_{i+1}-1,a_{i+1}-2,\ldots,a_{i+1}-\delta)$ where
$\delta=a_{i+1}-a_i+1$ (in particular $\delta\geq0$ and the face incident to
$(a_i,a_{i+1})$ has degree $\delta+2$).
\end{lemma}
\begin{proof} See \cite{Stanley}, or the detailed
discussion of the appendix.
\end{proof}
\begin{figure}
\centerline{\includegraphics[scale=.5]{DeuxTypesAretes}}
\caption{The dissection of a polygon and the two types of faces of
$\psi(\mathfrak{t})$}
\label{fig:typesaretes}
\end{figure}

The \emph{closure} of a well labeled $g$-tree $\mathfrak{t}$ with $n$ edges is
the graph drawing $\psi(\mathfrak{t})$ constructed as follows: Let $\mathfrak{p}$ be
the labelled $2n$-gon describing the face $f$ of $\mathfrak{t}$, and let $k$
be the number of vertices with label $1$ in $\mathfrak{p}$: these vertices
corresponds to \emph{corners} with label $1$ of $f$. Let $\mathfrak{t}'$ be
the map obtained by adding a vertex $v_0$ with label $0$ in $f$ and
$k$ edges that join this vertex to each of the corners with label $1$
of $f$: the map $\mathfrak{t}'$ has $k$ faces and the border of each face is a
polygon $\vec\mathfrak{p}_i$ with minimal label~$0$ (taken as root) and labels
that satisfies the Lukasiewicz condition (the variations are even in
$\{+1,0,-1\}$).  In each face of the map $\mathfrak{t}'$ (on $\mathcal{S}_g$),
that is in each polygon $\vec\mathfrak{p}_i$, the above lemma can thus be used
to add all the edges between corners with positive labels and their
predecessor, in the unique way that provides a map $\mathfrak{t}''$ on
$\mathcal{S}_g$. The closure $\psi(\mathfrak{t})$ of $\mathfrak{t}$ is the graph
drawing $\mathfrak{t}''-\mathfrak{t}$ on $\mathcal{S}_g$ obtained by removing the
edges of $\mathfrak{t}$ from $\mathfrak{t}''$.
\begin{lemma}\label{lem:close}
The graph drawing $\psi(\mathfrak{t})$ is a quadrangulation of genus $g$ with
$n$ edges.
\end{lemma}
\begin{proof}
According to Lemma~\ref{lem:luka} each face of $\mathfrak{t}'$ is incident
exactly once to an edge of $\mathfrak{t}$. Each edge $e$ of $\mathfrak{t}$ thus
separates two different faces, which are otherwise incident only to
edges of $\mathfrak{t}'-\mathfrak{t}$.  Moreover since the variation of labels are
opposite $\pm\delta$ on the two sides of $e$, the removal of $e$
creates a simply connected face of degree $\delta+2+(-\delta+2)-2=4$,
as illustrated by Figure~\ref{fig:typesaretes}. The removal of the $n$
edges of $\mathfrak{t}$ thus creates $n$ quadrangular faces.
\end{proof}

\subsection{The main theorem}
The main combinatorial result of this paper is the following theorem,
that states that not only $\phi(\mathfrak{q},v_0)$ is a well labelled map on
$\mathcal{S}_g$ but the mapping $\phi$ is more precisely a bijection.
\begin{theorem}\label{thm:bijection}
The opening $\phi$ is a bijection between
\begin{itemize}
\item pointed bipartite quadrangulations of genus $g$ that have $n$ faces, $2n$
edges, and $n+2-2g$ vertices ($i$ of which are at odd distance of the
basepoint), and
\item well labeled $g$-trees that have $n$ edges, and $n+1-2g$ vertices
($i$ of them having odd labels),
\end{itemize}
such that the labels of the $g$-tree associated to a bipartite
quadrangulation $\mathfrak{q}$ with basepoint $v_0$ give the distances of
vertices of $\mathfrak{q}$ to $v_0$.
\end{theorem}
\begin{proof}
The fact that $\phi(\psi(\mathfrak{t}))=\mathfrak{t}$ follows from the comparison of
Figure~\ref{fig:typesaretes} and Figure~\ref{fig:rules}: for the two
types of faces created in $\psi(\mathfrak{t})$, the edge $e$ is indeed
recovered correctly by the opening rules. The fact that
$\psi(\phi(\mathfrak{q},v_0))=(\mathfrak{q},v_0)$ follows from the fact that in
$\mathfrak{q}'=\mathfrak{q}\cup\phi(\mathfrak{q},v_0)$, each edge of $\mathfrak{q}$ joins a corner of
$\phi(\mathfrak{q},v_0)$ to its predecessor, and from the unicity in
Lemma~\ref{lem:luka}. An alternative direct proof is proposed in the appendix.
\end{proof}

In the enumerative context one usually prefers to deal with rooted
maps to avoid the discussion of symmetries.  The opening is readily
extended to rooted bipartite quadrangulations: define the image of a
rooted quadrangulation $(\mathfrak{q},\vec e)$ with root vertex $v_0$, to be
$(\phi(\mathfrak{q},v_0),\vec {e'})$ where $e'$ is the edge created in the root
face of $(\mathfrak{q},\vec e)$, oriented so that its origin is the endpoint of
$\vec e$ (observe that, according to the rules and the definition of
the root face, the endpoint of $\vec e$ is indeed incident to
$e'$).
\begin{corollary}
The opening $\phi$ extends to a bijection between
\begin{itemize}
\item rooted bipartite quadrangulations with genus $g$ that have $n$ faces, and
\item rooted well labeled $g$-trees that have $n$
edges.
\end{itemize}
\end{corollary}
\begin{proof}
By construction the origin of $\vec {e'}$ has label $1$ so that
$(\phi(\mathfrak{q},v_0),\vec {e'})$ is indeed a rooted well labeled tree.
Conversely given a rooted well labeled tree $\vec\mathfrak{t}=(\mathfrak{t},\vec
{e'})$ with root vertex $v$, taking as root edge of $\psi(\vec\mathfrak{t})$
the edge $\vec e$ of $\mathfrak{t}'$ with origin $v_0$ which follows $\vec
{e'}$ in counterclockwise direction around $v$ immediately yields the
unique possible preimage of $\vec\mathfrak{t}$.
\end{proof}

It turns out that for our purpose an even better variant consists in
taking a basepoint and a root independently. Define the image of a
rooted pointed bipartite quadrangulation $(\mathfrak{q},\vec e,v_0)$ to be
$(\phi(\mathfrak{q},v_0),\vec{e'},s)$ where $\vec{e'}$ is the new edge created
in the root face of $\mathfrak{q}$, oriented so that its origin is the
extremity of $\vec e$ with largest label, and where $s\in\{+1,-1\}$ is
a sign recording the orientation of $\vec e$ (say $+$ if $\vec e$ is
increasing with respect to the labeling).  Let moreover $\nu$ be the
relabeling mapping that simultaneously translates all labels of an
embedded map so that the root vertex label is 1. Then

\begin{corollary}\label{cor:embedded}
Opening followed by relabelling is a bijection $\nu\circ\phi$ between
\begin{itemize}
\item rooted pointed bipartite quadrangulations with genus $g$ that have $n$
faces, and
\item pairs consisting of a rooted embedded $g$-tree that
has $n$ edges and a sign $\pm1$.
\end{itemize}
\end{corollary}
\begin{proof}
In view of Theorem~\ref{thm:bijection}, $\phi$ can be used to map
bijectively rooted pointed bipartite quadrangulations $(\mathfrak{q},v_0,\vec
e)$ of genus $g$ with $n$ faces onto almost well labelled rooted
g-trees $(\phi(\mathfrak{q},v_0),\vec e)$ with $n$ edges (\emph{almost} well labeled
means the minimum label is 1 but the root vertex has not necessarily
label 1). Now $\nu$ is bijective between almost well labelled
$g$-trees with $n$ edges and embedded rooted $g$-trees with $n$ edges:
indeed given a rooted embedded map (with root vertex label 1 by
definition), there is a unique way to translate its labels so that the
minimum becomes 1.
\end{proof}

The point of this last corollary is that, as we shall see in
Section~\ref{sec:enumeration}, embedded $g$-trees are much easier to
count than well labeled $g$-trees.

\section{The enumeration of quadrangulations
via schemes}\label{sec:enumeration}

In view of Theorem~\ref{thm:bijection} and
Corollary~\ref{cor:embedded}, the enumeration of maps of genus $g$
according to the number of vertices, faces and edges can be reduced to
the enumeration of rooted well labeled or embedded $g$-trees.  It
turns out that rooted embedded $g$-trees are easier to deal with, so
that we shall rely on the following transposition of
Corollary~\ref{cor:embedded} in terms of generating series:
\begin{corollary}\label{cor:enum}
 The generating series
  \[
  \overrightarrow{Q_g}^\bullet(z)=\sum_{n\geq2g}\vec{q}_{g,n}^{\;\bullet}
  z^n,\quad \textrm{and}\quad T_g(z)=\sum_{n\geq2g}a_{g,n}z^n
  \]
  of rooted pointed bipartite quadrangulations of genus $g$ (with
  respect to the number of faces) and of rooted embedded $g$-trees
  (with respect to the number of edges) are related by the following
  equation:
  \begin{eqnarray*}
    \overrightarrow{Q_g}^\bullet(z)&=&2T_g(z).
  \end{eqnarray*}
\end{corollary}
Since a quadrangulation with genus $g$ and $n$ faces has $n+2-2g$
vertices, $\vec{q}^{\;\bullet}_{g,n}=(n+2-2g)\;\vec{q}_{g,n}$, and the
previous equation can also be rewriten in terms of the generating
series of rooted bipartite quadrangulations of genus $g$ as
\begin{equation}\label{for:enum}
Q_g(z)=\sum_{n\geq2g}\vec{q}_{g,n}z^n=
z^{2g-2}\int \overrightarrow{Q_g}^\bullet(y)\,y^{1-2g}\,dy
\end{equation}
with the initial condition $Q_g(z)=O(z^{2g})$.

\subsection{Planar maps and embedded trees}
Let $T\equiv T(z)=T_0(z)$ be the generating series of rooted embedded
trees with respect to the number of edges. A rooted embedded tree
$\vec\mathfrak{t}$ which has at least 1 edge can be decomposed into two rooted
trees $\vec\mathfrak{t}_1$ and $\vec\mathfrak{t}_2$ by deleting its root edge $e$. The
subtree $\vec\mathfrak{t}_1$ rooted at the origin of $e$ has root label 1, so
that it is again a rooted embedded tree. The subtree $\vec\mathfrak{t}_2$
rooted at the endpoint of $e$ has root label $\delta\in\{+1, 0, -1\}$
but, up to a translation of labels by $1-\delta$, it is also a rooted
embedded tree. This decomposition is a bijection
$\vec\mathfrak{t}\mapsto(\delta,\vec\mathfrak{t}_1,\vec\mathfrak{t}_2)$ between non empty
rooted embedded trees with $n$ edges and triples consisting of an edge
variation and two rooted embedded trees with a total of $n-1$
edges. Hence the equation
\begin{eqnarray*}
T(z)=\sum_{\vec\mathfrak{t}}z^{|\vec\mathfrak{t}|}=1+3\sum_{(\vec\mathfrak{t}_1,\vec\mathfrak{t}_2)}z^{1+|\vec\mathfrak{t}_1|+|\vec\mathfrak{t}_2|}=1+3zT(z)^2.
\end{eqnarray*}
The unique formal power series root of this quadratic equation
$T=1+3zT^2$ is
\[
T(z)=\frac{1-\sqrt{1-12z}}{6z}.
\]
In particular $a_n=[z^n]T(z)=\frac{3^n}{n+1}{2n\choose n}$ is the
number of embedded trees with $n$ edges.  For future reference, let us
also observe the relations
\begin{equation}
z\;=\;\frac{T-1}{3T^2},\qquad \qquad
zT'\;=\;\frac{T^2-T}{2-T},
\qquad\textrm{and}\qquad
1+\frac{2zT'}T\;=\;\frac T{2-T}.
\end{equation}
The enumeration of planar quadrangulations then directly follows from
Corollary~\ref{cor:enum}.
\begin{corollary}\label{cor:planar}
The generating series of planar rooted pointed quadrangulations satisfies
\[
    \overrightarrow{Q_0}^\bullet(z)\;=\;2T(z),
\]
and the number of planar rooted quadrangulations with $n$ faces is
\[
\vec q_{0,n}=\frac{\vec{q}^{\;\bullet}_{0,n}}{n+2}=\frac2{n+2}\cdot
\frac{3^n}{n+1}{2n\choose n}.
\]
\end{corollary}

\subsection{Reduced $g$-trees and tree grafting}

We say that a $g$-tree is {\it reduced} if it has no vertices of degree
one.  Upon deleting vertices of degree 1 iteratively, a reduced $g$-tree can
be extracted from any $g$-tree.

\begin{lemma}\label{lem:reduced}
There is a bijection
between rooted embedded $g$-trees with $n$ edges and pairs consisting
of a rooted embedded reduced $g$-tree $\vec\mathfrak{r}$ with $k$ edges and a forest
$(\vec\mathfrak{t}_1,\ldots, \vec\mathfrak{t}_{2k})$, where,
\begin{itemize}
 \item $\vec\mathfrak{t}_2,\dots,\vec\mathfrak{t}_{2k}$ are rooted embedded planar trees.
 \item $\vec\mathfrak{t}_1$ is either a rooted or a doubly rooted embedded planar tree,
\end{itemize}
and the total number of edges in
$(\vec\mathfrak{r};\vec\mathfrak{t}_1,\ldots,\vec\mathfrak{t}_{2k})$ is $n$.
\end{lemma}
\begin{figure}
\centerline{\includegraphics[scale=0.6]{smooth}}
\caption{A $1$-tree and its decomposition into a reduced $1$-tree and a
collection of rooted planar trees attached on its corners (only planar
trees which are not reduced to a single vertex are represented).}
\label{fig:reduced}
\end{figure}
\begin{proof}
Given a $g$-tree $\mathfrak{t}$, a unique reduced $g$-tree $\mathfrak{r}$ is obtained
by iteratively deleting in $\mathfrak{t}$ the vertices of degree $1$ until
none is left. At the end of this process, the deleted edges form a
forest of rooted embedded planar trees: one (possibly trivial) rooted
tree is attached to each corner of $\mathfrak{r}$ (see
Figure~\ref{fig:reduced}). The root $\vec e$ of $\vec\mathfrak{t}$, then
provides a root for $\vec\mathfrak{r}$: if $\vec e$ was not deleted it becomes
the root of $\vec\mathfrak{r}$, otherwise $\vec e$ belongs to one of the
deleted trees $\vec\mathfrak{t}_1$ and the root of $\vec\mathfrak{r}$ is taken to be the
arc of $\mathfrak{r}$ on the right hand side of which $\vec\mathfrak{t}_1$ is attached.

Once $\vec\mathfrak{r}$ is rooted, its corners are canonically ordered
starting with the corner on the right hand side of the root, and the
deleted trees can be arranged into an ordered list: the $g$-tree
$\mathfrak{t}$ can then be recovered from $\vec\mathfrak{r}$ and the ordered list
$(\vec\mathfrak{t}_1,\ldots,\vec\mathfrak{t}_{2k})$ of trees. Finally, when the root
of $\vec \mathfrak{t}$ is not an edge of $\vec\mathfrak{r}$ it must be recorded as a
secondary root of $\vec\mathfrak{t}_1$.
\end{proof}

Lemma~\ref{lem:reduced} immediately yields the following corollary.
\begin{corollary}\label{cor:reduce}
The generating series of rooted embedded $g$-trees $T_g$ and of
rooted embedded reduced $g$-trees $R_g$ are related by:
\begin{eqnarray*}
T_g(z)&=&R_g(zT(z)^2)\cdot \big(1+\frac{2zT'(z)}{T(z)}\big)\;=\;
R_g(zT^2)\cdot \frac T{2-T}.
\end{eqnarray*}
In terms of the primitive $\widehat R_g(t)$, satisfying
$\frac{t\partial}{\partial t}\widehat R_g(t)= R_g(t)$, the previous
formula reads:
\begin{eqnarray*}
T_g(z)&=&\frac{z\partial}{\partial z}\left(\widehat R_g(zT^2)\right).
\end{eqnarray*}
\end{corollary}
\begin{proof}
The decomposition of a rooted $g$-tree $\mathfrak{t}$ in a pair
$(\vec\mathfrak{r};\vec\mathfrak{t}_1,\ldots,\vec\mathfrak{t}_{2k})$ where $k$ is the number
of edges of $k$ is a combinatorial composition operation that
results in the composition of generating series:
\begin{eqnarray*}
T_g(z)&=&\sum_{\vec\mathfrak{t}}z^{|\vec\mathfrak{t}|}
\;=\;\sum_{\vec\mathfrak{r};\vec{\vec\mathfrak{t}}_1,\vec\mathfrak{t}_2\ldots,\vec\mathfrak{t}_{2k}\,\mid\,
k=|\vec\mathfrak{r}|}
z^{|\vec\mathfrak{r}|+|\vec{\vec\mathfrak{t}}_1|+|\vec\mathfrak{t}_2|+\ldots+|\vec\mathfrak{t}_{2k}|}\\
&=&\sum_{\vec\mathfrak{r}}z^{|\vec\mathfrak{r}|}\left(\sum_{\vec\mathfrak{t}}(1+2|\vec\mathfrak{t}|)z^{|\vec\mathfrak{t}|}\right)
\left(\sum_{\vec\mathfrak{t}} z^{|\vec\mathfrak{t}|}\right)^{2|\vec\mathfrak{r}|-1}
\;=\;R_g(zT(z)^2)\cdot(1+\frac{2zT'}T),
\end{eqnarray*}
where the notation $\vec{\vec\mathfrak{t}}_1$ stresses the fact that the first
tree can be doubly rooted: given a tree $\mathfrak{t}$ there are $2|\mathfrak{t}|$
ways to introduce a double root and one way not to.  The
multiplicative factor $1+2zT'(z)/T(z)$ can also be understood
directly, saying that the first rooted tree (with generating series
$T(z)$) can be replaced by a doubly rooted tree (with generating
series $2zT'(z)$).

The second expression can be checked by a direct comparison with the
first formula:
\begin{eqnarray*}
\frac{z\partial}{\partial z}\left(\widehat R_g(zT^2)\right)&=&
z(T^2+2zTT')\widehat R_g'(zT^2)\\&=&(zT^2)\widehat R_g'(zT^2)(1+2zT'/T)=
R_g(zT^2)\cdot \big(1+\frac{2zT'}{T}\big).
\end{eqnarray*}
\end{proof}

By definition the series $\widehat R_g$ is a generating series of
rooted maps in which rooted maps with $e$ edges are counted with a
weight $1/e$: it is tempting to think about it as a generating series
of unrooted maps, but then each unrooted map is counted with a weight
proportional to the inverse of the size of its automorphism group
(because maps with non trivial automorphisms have less than $2e$
distinct rootings).  In these terms the second expression of
Corollary~\ref{cor:reduce} could be understood directly as follows:
rooted $g$-trees are first constructed as unrooted by grafting trees
in an unrooted reduced $g$-tree, and then rooted. However a rigourous
proof along these lines requires a careful discussion of symmetries,
which is circumvented by working directly with rooted objects.

\subsection{The standard scheme of a reduced $g$-tree}
A \emph{labeled scheme} is a rooted $g$-tree without vertices of degree 1 and
2 that has integer labels on vertices. A scheme is \emph{standard} if
its labels form an integer interval with minimum 0.  Observe that the
labels of a scheme are not required to vary at most by one along
edges, and that in a standard scheme all the integers of the interval
must appear as labels.

Let $\vec\mathfrak{r}$ be a rooted reduced $g$-tree. By definition
the map $\vec\mathfrak{r}$ has no vertices of degree 1. Its vertices of degree
2 are organized into maximal paths, connected together at vertices of
degree at least 3. Let $\vec\mathfrak{s}_0$ and $\vec \mathfrak{s}$ be the maps obtained
from $\vec\mathfrak{r}$ as follows:
\begin{itemize}
\item To get $\vec\mathfrak{s}_0$ from $\vec \mathfrak{r}$, replace each maximal path
made of vertices of degree 2 by an edge, the path containing the root
of $\vec\mathfrak{r}$ providing a rooted edge for $\vec\mathfrak{s}_0$.
\item To get $\vec\mathfrak{s}$ from $\vec\mathfrak{s}_0$, standardize the labels of the
vertices, so that they form an integer interval with minimum label 0:
if the labels appearing on vertices of degree at least 3 in $\vec\mathfrak{r}$
are $\ell_0<\ell_1<\ldots<\ell_p$ then the corresponding labels in
$\vec\mathfrak{s}$ are $0,1,\ldots,p$ (a given label can appear on several
vertices of $\vec\mathfrak{s}_0$, so that $p$ may be smaller than the number of
vertices of $\vec\mathfrak{s}$.).
\end{itemize}
The maps $\vec\mathfrak{s}_0$ and $\vec\mathfrak{s}$ are labeled schemes, and $\vec\mathfrak{s}$
is standard: it is called \emph{the standard scheme of $\vec\mathfrak{r}$}. By
extension, $\vec\mathfrak{s}$ is called the standard scheme of $\vec\mathfrak{q}$ if
$\vec\mathfrak{r}$ was itself extracted from the $g$-tree $\vec\mathfrak{t}$
associated to a quadrangulation $\vec\mathfrak{q}$. Finally, given a rooted
standard scheme $\vec\mathfrak{s}$ with labels $\{0,\ldots,p\}$ and $p$
positive integers $\ell_1<\ldots<\ell_p$ let
$\vec\mathfrak{s}(\ell_1,\ldots,\ell_p)$ be the rooted labeled scheme obtained
by replacing labels $i$ by $\ell_i$ in $\vec\mathfrak{s}$.

Observe that on every maximal degree 2 path of $\vec\mathfrak{r}$, the labels
perform a sequence of small variations taken from $\{+1,0,-1\}$.  A
\emph{Motzkin walk} $w$ of length $\ell$ is defined as a finite
sequence $w_1\ldots w_\ell$ with $w_i\in\{+1,0,-1\}$. The quantity
$\sum_{i=0}^\ell w_i$ is called the \emph{increment} of $w$. A Motzkin
walk of increment $0$ is called a \emph{Motzkin bridge}. In these
terms, on every maximal path of $\mathfrak{r}$, the sequence of variations of
labels forms a {Motzkin walk}: hence, if the standard scheme $\vec\mathfrak{s}$
of $\vec\mathfrak{r}$ has $k$ edges, a $k$-uple of Motzkin walks
$(\mathfrak{m}_1,\ldots,\mathfrak{m}_k)$ can be extracted from $\vec\mathfrak{r}$, with $\mathfrak{m}_i$
the Motzkin walk read along the path of $\vec\mathfrak{r}$ corresponding to
$i$th edge of $\vec\mathfrak{s}$ in the canonical order.

\begin{figure}
\centerline{\includegraphics[scale=0.6]{fig8}}
\caption{A reduced $1$-tree and its rooted scheme.}
\label{fig:scheme}
\end{figure}

A $k$-uple of Motzkin walks is said to be \emph{compatible} with a
rooted standard scheme with $k$ edges if there exists an embedded
rooted reduced $g$-tree from which they can be both extracted. Observe
that the $g$-tree is unique up to translation of all labels, since it
is recovered by replacing the $i$th edge of the scheme by a chain of
vertices with variations given by the $i$th Motzkin walk.

\begin{lemma}\label{lem:bijection-scheme}
There is a bijection between embedded rooted reduced $g$-trees with
$n$ edges such that the root vertex has degree at least 3, and pairs
formed of a rooted standard scheme of genus $g$ with $k$ edges, and a
compatible $k$-uple of non empty walks with a total of $n$ steps.
\end{lemma}
\begin{proof}
In view of the definition of compatible $k$-uples of walks, it
suffices to show that if the pair $(\vec\mathfrak{s};(\mathfrak{m}_1,\ldots,\mathfrak{m}_k))$ is
extracted from embedded rooted reduced $g$-tree $\mathfrak{t}$ then $\mathfrak{t}$ can
be recovered from the pair: this is immediate upon replacing the $i$th
edge of $\vec\mathfrak{s}$ by a path with labels given by $\mathfrak{m}_i$, and choosing
the root to be the first edge of the first path.
\end{proof}

In particular, given a rooted standard scheme $\vec\mathfrak{s}$ and a
compatible $k$-uple of Motzkin walks $(\mathfrak{m}_1,\ldots,\mathfrak{m}_k)$ let $\vec
r(\vec\mathfrak{s};\mathfrak{m}_1,\ldots,\mathfrak{m}_k)$ be the unique corresponding rooted
reduced $g$-tree, and $\vec\mathfrak{s}_0(\vec\mathfrak{s};\mathfrak{m}_1,\ldots,\mathfrak{m}_k)$ be the
rooted labeled scheme extracted from $\vec
r(\vec\mathfrak{s};\mathfrak{m}_1,\ldots,\mathfrak{m}_k)$ before standardization.

\begin{lemma}\label{lem:compatible}
Let $\vec \mathfrak{s}$ be a rooted standard scheme with $k$ edges and labels
$\{0,1,\ldots,p\}$, and  let $\ell_1<\ldots<\ell_p$ be positive integers.

Then the set of compatible $k$-uples such that
$\vec\mathfrak{s}_0(\vec\mathfrak{s};\mathfrak{m}_1,\ldots,\mathfrak{m}_k)=\vec\mathfrak{s}(\ell_1,\ldots,\ell_k)$
is exactly the set of $k$-uples $(\mathfrak{m}_1,\ldots,\mathfrak{m}_k)$ such that, for
all $i$, $\mathfrak{m}_i$ has increment $\ell_{e_i^+}-\ell_{e_i^-}$, where
$e_i^-$ and $e_i^+$ are the labels of the origin and endpoint of the
$i$th edge $\vec e_i$ of $\vec\mathfrak{s}$.
\end{lemma}
\begin{proof}
If a $k$-uple is compatible with $\vec\mathfrak{s}$ and induces
$\ell_0\ldots\ell_p$ then the labels of the corresponding reduced
$g$-tree satisfy the conditions of the lemma. Conversely, given
$\ell_0,\ldots,\ell_p$, a corresponding embedded reduced $g$-tree is
obtained by replacing, for $i=1,\ldots,k$, the $i$th edge $\vec e_i$
of $\vec\mathfrak{s}$ by a labelled path constructed as follows: if
$\mathfrak{m}_i=w_1\ldots w_\ell$ and $e_i^-$ is the label of the origin of
$\vec e_i$ then the inserted path has length $\ell$ and its $j$th
vertex has label $\ell_{e}+\sum_{m=1}^jw_m$, for
$j=0,\ldots,\ell$. The condition on increments ensures that each
vertices of $\vec\mathfrak{s}$ get the same label from all its incident edges.
A root can be chosen arbitrarily on the first path and labels
simultaneously translated to obtain an embedded rooted reduced
$g$-tree.
\end{proof}

Let $\vec\mathfrak{s}$ be a rooted standard scheme with $v$ vertices, $k$ edges
and labels $\{0,\ldots,p\}$.  We define the \emph{weight} of $\vec\mathfrak{s}$
as the following power series:
\begin{eqnarray*}
W_{\vec\mathfrak{s}}(t) =
\frac{1}{k}
\sum_{0<\ell_1<\ldots<\ell_{p}}
  \prod_{i=1}^kM_{|\ell_{e_i^+}-\ell_{e_i^-}|}(t),
\end{eqnarray*}
where $e_i^-$ and $e_i^+$ denote the label of the extremities of the
$i$th edge $\vec e_i$ of $\vec \mathfrak{s}$, and, for all $j\geq 0$,
$M_{j}(t)$ is the generating series of non-empty Motzkin walks of
increment $j$ with respect to the length:
$M_j(t)=\sum_{\mathfrak{m}}t^{|\mathfrak{m}|}$, where the sum is over all Motzkin walks
with increment $j$ and length at least 1.

\begin{lemma}
\label{lemma:weight}
The primitive $\widehat{R_g}(t)$ of the generating series of embedded
rooted reduced $g$-trees satisfies
$$
\widehat{R_g}(t) = \sum_{\vec\mathfrak{s}} W_{\vec\mathfrak{s}}(t)
$$ where the sum is taken over all rooted standard schemes of genus $g$.
\end{lemma}

\begin{proof}
Let us group together in a series $R_{g,k}(t)$ the contributions to the generating
series $R_{g}(t)$ of the embedded reduced $g$-trees whose standard
scheme has $k$ edges, so that
$R_g(t)=\sum_k R_{g,k}(t)$. Then $2kR_{g,k}(t)$ is the generating series of rooted
embedded reduced $g$-trees whose standard scheme has $k$ edges and carries a
secondary root-edge leaving a vertex of degree at least $3$: indeed, each maximal
path of a given reduced $g$-tree provides $2$ choices of such a secondary root.

Now, these rooted embedded reduced $g$-trees having a secondary root can also be obtained
by considering first a rooted reduced $g$-tree with a root vertex of degree at least $3$
(and whose standard scheme has $k$ edges), and then choosing a root edge. Hence we have:
\begin{eqnarray}
\label{eq:doublerooting1}
2k R_{g,k}(t) = 2\frac{td}{dt}\sum_{|\vec\mathfrak{s}|=k} \widetilde{R}_{\vec\mathfrak{s}}(t)
\end{eqnarray}
where the sum is taken over rooted standard schemes of genus $g$ with $k$ edges, and where
$\widetilde{R}_{\vec\mathfrak{s}}(t)$ is the generating series of embedded reduced $g$-trees
of scheme $\vec\mathfrak{s}$ with a root vertex of degree at least $3$
(the derivative accounts for the choice of the root edge, and the factor
$2$ for the choice of its orientation).

Now, in view of Lemmas~\ref{lem:bijection-scheme}--\ref{lem:compatible}, for each scheme
$\vec\mathfrak{s}$ with $k$ edges, the
generating series $\widetilde R_{\vec\mathfrak{s}}(t)$
is obtained by summing over all relabellings and compatible $k$-uples
of Motzkin paths. Therefore:
\begin{eqnarray}
\label{eq:doublerooting2}
\widetilde R_{\vec\mathfrak{s}}(t)=
\sum_{0<\ell_1<\ldots<\ell_{p}}
  \prod_{i=1}^kM_{|\ell_{e_i^+}-\ell_{ e_i^-}|}(t)
\end{eqnarray}
Putting Equations~\ref{eq:doublerooting1} and ~\ref{eq:doublerooting2} together and using the
definition of $W_{\vec\mathfrak{s}}$ gives:
$$
R_{g,k}(t) = \frac{td}{dt}\sum_{|\vec\mathfrak{s}|=k} W_{\vec\mathfrak{s}}(t).
$$
Summing on $k$ and comparing with the definition of $\widehat{R_g}(t)$ yields the result.
\begin{comment}
Let us group together in a series $R_{\vec\mathfrak{s}}$(t) the contributions
to the generating series $R_g(t)$ of the reduced $g$-trees sharing a same
rooted standard scheme $\vec\mathfrak{s}$, so that
$R_g(t)=\sum_{\vec\mathfrak{s}}R_{\vec\mathfrak{s}}(t)$.
If $\vec \mathfrak{s}$ is a standard scheme with $k$ edges, then
$2kR_{\vec \mathfrak{s}}(t)$ is the generating series of embedded rooted
reduced $g$-trees of scheme $\vec\mathfrak{s}$ carrying a secondary root edge
leaving a vertex of degree at least $3$: indeed, each maximal path
of a given reduced $g$-tree provides two choices of such a secondary root.

These rooted reduced $g$-trees having a secondary root
can also be obtained by considering first
a rooted reduced $g$-tree with a root vertex of degree at least $3$, and
then choosing a root edge.
Now, in view of Lemmas~\ref{lem:bijection-scheme}--\ref{lem:compatible}, the
generating series of reduced $g$-trees of scheme $\vec\mathfrak{s}$ with a root vertex of degree
at least $3$
is obtained by summing over all relabellings and compatible $k$-uples
of Motzkin paths. Therefore:
\begin{eqnarray*}
2k\,R_{\vec\mathfrak{s}}(t)=2\frac{t\partial}{\partial
  t}\left(\sum_{0<\ell_1<\ldots<\ell_{p}}
  \prod_{i=1}^kM_{|\ell_{e_i^+}-\ell_{ e_i^-}|}(t)\right).
\end{eqnarray*}
where the derivative accounts for the choice of the root edge, and the factor
$2$ for the choice of its orientation.

Using the last relation to rewrite $R_g(t)=\sum_{\vec\mathfrak{s}}R_{\vec\mathfrak{s}}(t)$
and comparing with the definition of $\widehat{R_g}(t)$ yields the
result.
\end{comment}
\end{proof}

\subsection{The algebra of Motzkin walks}

A Motzkin walk is \emph{primitive} if it has increment $-1$ but none
of its prefix has increment $-1$. In other terms a Motzkin walk
$w=w_1\ldots w_\ell$ is primitive if it satisfies the \L ukasiewicz
property: $\sum_{i=1}^{\ell}w_i=-1$ but for all $j<\ell$,
$\sum_{i=1}^{\ell}w_i\geq0$.

Let $U\equiv U(t)=\sum_{w}t^{|w|}$ be the generating series of
primitive Moztkin walks according to the length, and $B\equiv
B(t)=M_0(t)$ be the generating series of non-empty bridges.  Using a
decomposition at the first step for $U$, and at the first return to
the $x$-axis for $B$, one gets:
\begin{eqnarray*}
U&=&t(1+U+U^2)\\
B&=&t(1+2U)(1+B)\;=\;\frac{t(1+2U)}{1-t(1+2U)}.
\end{eqnarray*}
Then the explicit value of $U$ and $B$ are
\begin{eqnarray*}
U=\frac1{2t}(1-t-((1-2t-3t^2)^{1/2}),&\textrm{ and } &
1+B=\frac1{(1-2t-3t^2)^{1/2}}.
\end{eqnarray*}
In terms of $U$, the series $B$ satisfies
\begin{eqnarray*}
B=\frac{U(1+2U)}{1-U^2},&\textrm{ and }&
1+B=\frac{1+U+U^2}{1-U^2}.
\end{eqnarray*}
Decomposing walks at their last passage time at each positive
integer, one obtains the generating function of Motzkin walks
of increment $i>0$:
\begin{eqnarray*}
M_i(t) = (1+B) U^i
\end{eqnarray*}

The algebra of Laurent power series generated by the series $U$ contains
$t$ since
\[
t=\frac{U}{1+U+U^2}=\frac1{U^{-1}+1+U}.
\]
More generally we would like to characterize rational expressions in
$U$ that are in fact rational expressions in $t$. Obviously these
expressions are symmetric in the exchange $U\leftrightarrow U^{-1}$.
This is also a sufficient condition since the polynomials
$(U+1+U^{-1})^k$ form a base of the set of polynomials in
$\{U,U^{-1}\}$ that are symmetric in these two indeterminates.

\begin{lemma}
A rational series in $U$ is a rational series in $t$ if and only if it
is symmetric in the exchange $U\leftrightarrow U^{-1}$.
\end{lemma}

\subsection{The torus}
Let $\mathfrak{r}$ be a reduced $1$-tree with $k$ edges, and let $d_i$ be the
number of vertices of degree $i$ in $\mathfrak{r}$. Then the vertex-edge
incidence relation and Euler's formula give the following 2 relations:
\[
\left\{
\begin{array}{rcl}
2k &=&\sum_{i\geq1} id_i,\\
k&=&1+\sum_{i\geq1} d_i.
\end{array}
\right.
\]
Eliminating $k$ and recording that $d_1=0$ since $\mathfrak{r}$ is reduced,
this yields
\[
\sum_{i\geq2} (i-2)d_i=2.
\]
Hence, apart from vertices of degree 2, there can be only one vertex
of degree 4 ($d_3=0$, $d_4=1$) or two vertices of degree 3 ($d_3=2$,
$d_4=0$). Let us compute the standard schemes and weights associated to these
two types of reduced $1$-trees:
\begin{description}
\item[1 vertex of degree 4] If the 1-tree consists of 1 vertex of
degree 4 and vertices of degree 2, its standard scheme has just 1 vertex of
degree 4 and 2 edges that are loops. There is a unique rooted $1$-tree
$\vec\mathfrak{t}_1$ with one vertex of degree four, and giving label 0 to its
unique vertex we obtain the unique rooted standard scheme $\vec\mathfrak{s}_1$ with 1
vertex.  The associated weight is therefore
\[W_{\vec\mathfrak{s}_{1}}=\frac{1}{2}M_0^2=\frac12B^2
=\frac12\frac{(1+2U)^2U^2}{(1-U)^2(1+U)^2}.\]

\item[2 vertices of degree 3] If instead the 1-tree consists of two
vertices of degree 3 and vertices of degree 2, its standard scheme has two
vertices of degree 3 and 3 edges connecting them. There is again a
unique rooted $1$-tree with 2 vertices of degree 3 but the choice of a
label $a$ for the root vertex and $b$ for the second vertex yields
three different rooted standard schemes $\vec\mathfrak{s}_2,\vec\mathfrak{s}_3,\vec\mathfrak{s}_4$:
\begin{itemize}
\item $a=b=0$: in this case the endpoints of all three edges have
label 0, so that the associated weight is
\[W_{\vec\mathfrak{s}_{2}}=\frac{1}{3}B^3\;=\;
\frac13\frac{(1+2U)^3U^3}{(1-U)^3(1+U)^3}.
\]
\item $a=0$, $b=1$: in this case the associated weight is
\begin{eqnarray*}
W_{\vec\mathfrak{s}_{3}} &=&
\frac{1}{3} \sum_{\ell_1>0} \left((1+B)U^{\ell_1} \right)^3
\;=\;\frac13(1+B)^3\frac{U^3}{1-U^3}\;=\;
\frac23\frac{(1+U+U^2)^2U^3}{(1-U)^4(1+U)^3}
\end{eqnarray*}
\item $a=1$, $b=0$: this case yields the same weight as the previous one,
$W_{\vec\mathfrak{s}_{4}}=W_{\vec\mathfrak{s}_3}$.
\end{itemize}
\end{description}
Summing over the different cases, we get
\begin{eqnarray*}
\widehat{R_1}&=& W_{\vec\mathfrak{s}_{1}} +
  W_{\vec\mathfrak{s}_{2}} +W_{\vec\mathfrak{s}_{3}}+W_{\vec\mathfrak{s}_4} \\
&=&
\frac{U^{-1}+4+U}{2((1-U)(1-U^{-1}))^2(1+U)(1+U^{-1})}.
\end{eqnarray*}
We thus obtained $\widehat{R_1}$ as a rational function of $U$. Its
symmetry w.r.t. the exchange $U\leftrightarrow U^{-1}$ shows that it is in
fact a rational function of $t$: indeed one easily checks that
\[
\widehat R_1\;=\;\frac{t^2(1+3t)}{2(1-3t)^2(1+t)}.
\]
In view of Corollary~\ref{cor:reduce} we obtain the generating
function of rooted $1$-trees as
\[
T_1(z)=\frac{z\partial}{\partial z}\widehat R_1(zT(z)^2)
\]
and deduce from Corollary~\ref{cor:enum} an expression for the
generating series of pointed rooted bipartite quadrangulation on the
torus as $\overrightarrow{Q_g}^\bullet(z)=2T_1(z)$.  However, in view
of Formula~\ref{for:enum}, one can derive directly the generating
series of rooted bipartite quadrangulations on the torus from
$\widehat R_1$:
\begin{eqnarray*}
Q_1(z)&=&\int \frac{dy}{y}\, \overrightarrow{Q_1}^\bullet(y)\;=\;
2\int \frac{dy}{y}\frac{yd}{dy}\widehat R_1(yT(y)^2)
\\
&=&2\widehat R_1(zT(z)^2)\;=\;2\widehat R_1({\textstyle\frac{T(z)-1}3})
\;=\;\frac{(T-1)^2T}{3(2-T)^2(2+T)},
\end{eqnarray*}
in agreement with the result of \cite{BeCa}.

\subsection{General surfaces}
In general the incidence and Euler relations for reduced $g$-trees
with $k$ edges and $d_i$ vertices of degree $i$ are
\[
\left\{
\begin{array}{rcl}
2k &=&\sum_{i\geq1} id_i,\\
k&=&2g-1+\sum_{i\geq1} d_i.
\end{array}
\right.
\]
Eliminating $k$ and using $d_1=0$, this yields
\[
\sum_{i\geq2}(i-2)d_i=4g-2.
\]
There is thus again a finite number of possible combinations for the
$d_i$ with $i\geq3$: in particular the two extremal possibilities in
terms of number of edges are:
\begin{itemize}
\item $d_{4g}=1$, and $d_i=0$ otherwise, which leads to schemes with 1
vertex of degree $4g$ and $2g$ edges, the minimal number of edges for
a scheme of genus $g$.
\item $d_3=4g-2$, and $d_i=0$ otherwise, which leads to schemes with
$4g-2$ vertices of degree 3 and $6g-3$ edges, the maximal number of
edges for a scheme of genus $g$.
\end{itemize}

Let $\vec\mathfrak{s}$ be a rooted standard scheme with $q$ vertices and $k$ edges
($k=2g-1+q$), Let us call $p$ the number of distinct nonzero labels in
$\vec\mathfrak{s}$ (in particular $0\leq p\leq q$), $\mathfrak{e}$ the set of edges with
equal extremities, and $\mathfrak{e}'$ its complement.  Then we have by
definition:
\begin{eqnarray*}
W_{\vec\mathfrak{s}}&=&\frac1k B^{|\mathfrak{e}|}\sum_{0<\ell_1<\ldots<\ell_{p}}
\prod_{e\in \mathfrak{e}'}M_{|\ell_{e_-}-\ell_{e_+}|},
\end{eqnarray*}
where $e_-$ and  $e_+$ denote the vertex labels of the extremities
of the edge $e$ of $\mathfrak{e}'$.

Observe that for $0\leq i<i'\leq v_{\neq}$, we have
$\ell_{i}<\ell_{i'}$ and
\[
M_{\ell_{i'}-\ell_{i}}=(1+B)U^{\ell_{i'}-\ell_i}=(1+B)\prod_{j=i+1}^{i'}U^{\ell_{j}-\ell_{j-1}},
\]
so that
\begin{eqnarray*}
W_{\vec\mathfrak{s}}&=&\frac1k B^{|\mathfrak{e}|}(1+B)^{|\mathfrak{e}'|}
\sum_{0<\ell_1<\ldots<\ell_{p}}
\prod_{e\in \mathfrak{e}'}\prod_{j=e_-+1}^{e_+ }U^{\ell_{j}-\ell_{j-1}}.
\end{eqnarray*}
Since the expression summand only involves the differences
$\delta_j=\ell_{j}-\ell_{j-1}$, the sum can be rewritten in terms of
these $p$ new variables:
\begin{eqnarray*}
W_{\vec\mathfrak{s}}&=&\frac1k B^{|\mathfrak{e}|}(1+B)^{|\mathfrak{e}'|}
\sum_{\delta_1,\ldots,\delta_{p}}
\prod_{e\in \mathfrak{e}'}\prod_{j=e_-+1}^{e_+}U^{\delta_j},
\end{eqnarray*}
where the $\delta_j$ are independant summation indices over positive
integers.  Now for each couple $(j,e)$ such that ${e_-}< j\leq e{_+}$
a contribution $U^{\delta_{j}}$ is obtained. Let $d(j)$ denote the
number of edges $e$ such that the couple $(j,e)$ satisfies the previous
condition. Observe that the $d(j)$ only depend on $\vec\mathfrak{s}$, not on the
$\delta_j$. Then
\begin{eqnarray*}
W_{\vec\mathfrak{s}}&=&\frac1k B^{|\mathfrak{e}|}(1+B)^{|\mathfrak{e}'|}
\sum_{\delta_1,\ldots,\delta_{v_p}}
\prod_{j=1}^{p}U^{d(j)\delta_j}\\
&=&\frac1kB^{|\mathfrak{e}|}(1+B)^{|\mathfrak{e}'|}
\prod_{j=1}^{p}\frac{U^{d(j)}}{1-U^{d(j)}}.
\end{eqnarray*}
Setting $e_==|\mathfrak{e}|$ and $e_{\neq}=|\mathfrak{e}'|$, and expressing $B$ in terms of
$U$ we obtain
\begin{eqnarray*}
W_{\vec\mathfrak{s}}
&=&\frac1k\frac{U^{e_=}(1+2U)^{e_=}(1+U+U^2)^{e_{\neq}}}{(1-U^2)^{k}}
\prod_{j=1}^{p}\frac{U^{d(j)}}{1-U^{d(j)}}.
\end{eqnarray*}

In view of Lemma \ref{lemma:weight}, the generating series of reduced labeled
$g$-trees is obtained upon summing these individual contributions for
all rooted standard schemes of genus $g$.

\begin{theorem}\label{thm:genusg}
Let $\mathcal{W}_g$ denote the (finite) set of rooted standard schemes of genus
$g$. Given such a standard scheme $\vec\mathfrak{s}$ with $k$ edges and labels
$\{0,1,\ldots,p\}$, let $e_=$ denote the number of edges with equal
labels at both ends, and $e_{\neq}=k-e_=$. For $j=1,\ldots,p$, denote
moreover by $d(j)$ the number of edges $e$ with endpoint labels
satisfying $e_-<j\leq e_+$, and $d=\sum_{j=1}^pd(j)$.  Then
\begin{eqnarray}
\label{eq:WgU}
\widehat R_{g}(t)
&=&
\sum_{\vec\mathfrak{s}\in\mathcal{W}_g}
\frac1{k}\frac{U^{d+e_=}(1+2U)^{e_=}(1+U+U^2)^{e_{\neq}}}
{(1-U)^{k+p}(1+U)^{k}}
\prod_{j=1}^{p}\frac1{1+U+\ldots+U^{d(j)-1}}
\end{eqnarray}
where $U$ is the formal power series in $t$ satisfying $U=t(1+U+U^2)$. Moreover
\[
   T_g(z)=\frac{z\partial}{\partial z}\widehat R_g(zT^2),\qquad
    \overrightarrow{Q_g}^\bullet(z)=2T_g(z)
\]
where $T$ is the formal power series in $z$ satisfying $T=1+3zT^2$.
\end{theorem}
In particular we expressed $\overrightarrow{Q_g}^{\bullet}(z)$ as a
rational function of $U(zT^2)$, which is an algebraic function of
degree 4. It is proved however in \cite{BeCa} that $Q_g(z)$ is in fact
a rational function in $z$ and $\sqrt{1-12z}$.  One can verify that
this result implies that our series $\widehat R_g(t)$ is in
fact a rational function in $t$, or in other terms that the expression
of $\widehat R_g(t)$ in terms of $U$ is in fact symmetric in the
exchange $U\leftrightarrow U^{-1}$. We are currently unable to give a
combinatorial proof of this fact.

\subsection{Asymptotics}

In Equation~(\ref{eq:WgU}), there are a finite number of critical
values of $U$, all being roots of unity, and $U=1$ is one of them.  As
a fuction of $t$, $U$ reaches the value $U=1$ at its singularity
$t=1/3$. Moreover, $U$ being a power series in $t$ with positive
coefficients, one has $\left|U(t)\right|\leq 1$ for every complex
number $t$ with $|t|\leq 1/3$, with equality only at $t=1/3$. This
implies that $t=1/3$ is the only dominant singularity of $R_g(t)$.
Finally, $U(t)$ is an algebraic function, which admits a Puiseux expansion
at its singularity:
\[
U=1-\sqrt{3}\sqrt{1-3t}+O(1-3t).
\]
This implies the following corollary:

\begin{corollary}
The dominant singularity of the algebraic function $\widehat R_g(t)$ is at
$t=1/3$, around which the following Puiseux expansion holds:
\[
\widehat R_g(t)=\sum_{\vec\mathfrak{s}\in\mathcal{W}_g}
\frac1{k}\left(\frac32\right)^{k}
\left(\frac{1}{\sqrt3\sqrt{1-3t}}\right)^{k+p}
\prod_{j=1}^{p}\frac1{d(j)}
\;\cdot\;(1+O(\sqrt{1-3t})),
\]
where for each $\vec\mathfrak{s}$ in the summation, $k$ is the number of
edges and $\{0,1,\ldots,p\}$ the set of distinct labels.
\end{corollary}
The dominant terms in this sum are given by the standard schemes $\vec\mathfrak{s}$ with
$k+p$ maximal: $p$ is at most $q-1$ if $\vec\mathfrak{s}$ has $q$ vertices and
all labels are distinct. Then $k+q-1=2q+2g-2$, which is maximal for
$q=d_3=4g-2$, resulting in $k+q-1=10g-6$.
\begin{corollary}
Let $\mathcal{W}^m_g$ denote
the set of rooted standard schemes of genus $g$ with $4g-2$ vertices of degree
3 that are labelled by distinct integers. Then
\[
\widehat R_g(t)=
\frac1{6g-3}
\frac{3^g}{2^{6g-3}}
\left(
\sum_{\vec\mathfrak{s}\in\mathcal{W}^m_g}\prod_{i=1}^{4g-3}\frac1{d(i)}
\right)
\left(\frac{1}{{1-3t}}\right)^{5g-3}
\;\cdot\;(1+O(\sqrt{1-3t})).
\]
\end{corollary}

In order to obtain the asymptotic behavior of
$\overrightarrow{Q_g}^\bullet(z)$, we need to consider the behavior of
$T$: this algebraic series has a unique dominant singularity at $z=1/12$ and
 \[T=2-2\sqrt{1-12z}+O(1-12z),\] so that
\[zT^2=\frac{T-1}3=\frac13-\frac2{3}\sqrt{1-12z}+O(1-12z).\]
Since $T$ is a power series in $z$ with positive coefficients, one has
$\left|zT^2\right|<1/3$ for every $z\neq1/12$ such that $|z|\leq
1/12$, so that we can compose the singular expansions of $T$ and
$\widehat R_g$ in the expression
$\overrightarrow{Q_g}^\bullet(z)=\frac{zd}{dz}\widehat R_g(zT^2)$ of
Corollary~\ref{cor:enum} to obtain:
\begin{corollary}
The algebraic series $\overrightarrow{Q_g}^\bullet(z)$ has a unique
dominant singularity at $z=1/12$, around which the following Puiseux
expansion holds:
\begin{eqnarray*}
\label{eq:devQ_g}
\overrightarrow{Q_g}^\bullet(z)&=&\frac{5g-3}{6g-3} \frac{3^g}{2^{11g-6}}
\left(
\sum_{\vec\mathfrak{s}\in\mathcal{W}^m_g}\prod_{i=1}^{4g-3}\frac1{d(i)}
\right)
\left(\frac{1}{\sqrt{1-12z}}\right)^{5g-1}\cdot(1+O((1-12z)^{1/4})\\
\end{eqnarray*}
\end{corollary}

It is a well known fact that algebraic functions are amenable to singularity
analysis (see \cite{FlOd,FlSe}). In other words, classical transfer theorems
apply to the previous expansion, leading to:
\begin{corollary}\label{cor:genusg}
The number $\vec q^{\,\bullet}_{g,n}$ of rooted pointed bipartite
quadrangulations of genus $g$ with $n$ faces satisfies:
\begin{eqnarray*}
\vec
q^{\,\bullet}_{g,n}&\sim&\frac{1}{\Gamma\left(\frac{5g-1}2\right)}
\frac{5g-3}{6g-3}\frac{3^g}{2^{11g-6}}
\left( \sum_{\vec\mathfrak{s}\in\mathcal{W}^m_g}\prod_{i=1}^{4g-3}\frac1{d(i)} \right) \cdot
{n^{\frac{5g-3}{2}}}\cdot 12^n.
\end{eqnarray*}
\end{corollary}

Recalling that $ q^\bullet_{g,n} = (n+2-2g) \vec q^{\,\bullet}_{g,n} $
and using the product relation
$\Gamma\left(\frac{5g-1}2\right)=\frac{5g-3}2\Gamma\left(\frac{5g-3}2\right)$,
we finally have:
\begin{corollary}
The number of rooted bipartite quadrangulations of genus $g$ with $n$
faces satisfies
\begin{eqnarray*}
q_{g,n}&\sim&\frac{3^g}{(6g-3)2^{11g-7}\Gamma\left(\frac{5g-3}2\right)}
\left(
\sum_{\vec\mathfrak{s}\in\mathcal{W}^m_g}\prod_{i=1}^{4g-3}\frac1{d(i)}
\right)
\cdot
{n^{\frac52(g-1)}}\cdot 12^n.
\end{eqnarray*}
\end{corollary}

Observe that the maps in $\mathcal{W}^m_g$ are vertex labeled rooted
maps with $4g-2$ vertices of degree 3, one face and degree $g$. Their
number is $(4g-2)!\varepsilon_g$ where $\varepsilon_g$ is the number
of cubic maps of genus $g$ with one face (or dually triangulations
with one vertex), known to be \cite{WaLe}:
\[
\varepsilon_g
=\frac{2}{12^{g}}\frac{(6g-3)!}{g!(3g-2)!}.
\]
In particular this allows to give bounds on the constant
$\sum_{\vec\mathfrak{s}\in\mathcal{W}^m_g}\prod_i\frac1{d(i)}$. For fixed $g$, this
constant is in principle a computable finite sum.  However, in
practice, since the number of maps in $\mathcal{W}^m_g$ grows
superexponentially in $g$, the computation is difficult to perform in
a reasonable time. In particular we were able to obtain in this way
the explicit value of the constants only for $g=1,2$, leading to the
following asymptotics, in agreement with \cite{BeCa}:
$$q_{1,n} \sim \frac{1}{24}\cdot 12^n \;\mbox{ and }\;
 q_{2,n}\sim\frac{7}{4320\sqrt{\pi}}\cdot n^{5/2}\cdot 12^n.$$ Several
 different explicit non linear recursions are known for these
 constants (see \cite{BeCa,DFGiZJ,Witten}), but we were unable to
 derive them from our expressions.

\section{Conclusion}

As in the planar case, our main bijection maps the distances to the
basepoint of a quadrangulation onto the labels of vertices of the
associated $g$-tree.  In particular it allows to prove that the
distances of a random vertex to the basepoint in a uniform random
quadrangulation with $n$ faces is again of order $n^{1/4}$: a detailed
analysis in this direction was recently done in \cite{Mi07} for
the Bolzmann distribution on quadrangulations of genus $g$. A natural
problem, partially considered there, is more generally to construct a
continuum limit of large quadrangulations in this $n^{1/4}$ scaling:
in view of the results of \cite{LG,LGPa} in the planar case, a
continuum limit of quadrangulations of genus $g$ is expected to have
the topology of $\mathcal S_g$.

We conjecture that the resulting \emph{continuum random
quadrangulation of genus $g$} would be universal enough to describe
the continuum limit of all models of uniform random maps with simple
face degree or connectivity constraints, but also the continuum limit
of uniform random graphs with $n$ vertices and minimum genus $g$.
\medskip

As we have seen the dominant terms in the asymptotic of the number of
maps on a surface of genus $g$ arises from maps with schemes that have
the maximum number of vertices and edges. More precisely with
probability going to 1 as $n$ goes to infinity, a random map of genus
$g$ has a scheme with $4g-2$ vertices of degree 3.

The asymptotic behavior appears to have an interesting structure. As
shown in \cite{Chapuy} the more general construction of Bouttier et al
\cite{BDFG} in terms of labeled mobiles extends to higher genus in a
similar way as our original quadrangular construction. As a result one
obtains a more general class of labeled $g$-trees, say
$g$-mobiles. The decomposition of \cite{Chapuy} is more involved but
leads to the \emph{same dominant standard schemes}, with weights involving,
instead of $U$ and $T$, a finite number of algebraic series depending
on the set of allowed degrees.  In particular the same constant
\[
\tau_g=\sum_{\vec\mathfrak{s}\in\mathcal{W}^m_g}\prod_{i=1}^{4g-3}\frac1{d(i)}
\]
drives the multiplicative constant in the asymptotic behavior, in
agreement with the pattern that was observed by \cite{Gao}, and with the
universality described in the physics literature \cite{DFGiZJ}.

\begin{acks}
This paper is based in part on early unpublished works of the last two
authors \cite{Ma:PhD,Sc:PhD} in their PhD theses under the direction
of Robert Cori.  We wish here to express our warm thanks to Robert
Cori for his interest and support for this project. We also thank
Gregory Miermont for communicating us \cite{Mi07} and for
interesting discussions.
\end{acks}

\bibliographystyle{alpha}

redpajama_set_name: RedPajamaArXiv


Book a locksmith to change the keys on moving day at your new home. Arrange time off work on moving day. Ensure new home will be thoroughly cleaned, oven cleaned, carpet steam cleaned before your move and original home after your move. how to change photos to srgb on mac Cubic Castles is a game app for smartphones that places you in complete control of the experience as you make a record and claim your particular bit of the amusement world to call your particular domain.
However, everything they steal goes to poor peasants of cubic castles and helps them survive upcoming days, and even weeks. We were able to capture a photo of these gold-thirsty bandits, cough while 20thRainyDay died over 100 times trying to complete the green course cough .
A Clay Lump is a material found in Natural Mines (Forest Mines). It is dropped by Raw Clay. How to make: Using an Extractor with mud as an ingredient and oil as fuel. It is dropped by Raw Clay. How to make: Using an Extractor with mud as an ingredient and oil as fuel.
A set of modernized 3D pong style games combining the best features of squash and tennis. The game space is a cubic room. The back wall is defended by your opponent (the computer) and the front wall (behind you) is defended by you.
Cubic Castles is a game app for smartphones that places you in complete control of the experience as you make a record and claim your particular bit of the amusement world to call your particular domain.


Home/Publishing • Rants • Reading • Writing /To Free, Or Not To Free?
Much of my research into digital book promotion suggested that freebies are a great way to get new readers to take a chance on your work, inspire good will with a potential long term readership, and create buzz for your work as a whole and you as an author. It's also very easy to do with digital work, simple as giving away ones and zeros.
Is it effective? I've given away over 1,500 digital copies this year between Amazon and my website, and I've yet to see it pay off for me … at least in the short term.
The opposing theory about freebies is that they devalue your work and foster a sense entitlement in your readership. I think this is true to a point. I know some readers who never pay for books because they never have to. There are so many free books available (not even counting piracy sites) that they could read non-stop for the rest of their lives and never run out of free books. I also know readers who will go on to buy your other work after reading and liking something of yours they got for free.
I will continue to offer freebies for a while, at least until all of my digital chaps are out of Kindle Unlimited. After that I'm going to reevaluate the practice. The free flash fiction on Knightmares is another thing. I happen to enjoy doing them and don't mind giving those away, so they will continue indefinitely.
That said, my digital Humor/Crime chapbook BIG TROUBLE IN LITTLE BOOTS is free on Amazon from May 17th (today) until May 21st. Get it while the gettin's free!


instrument installation (hook up) presented by ian. instrument installation (hook up) presented by ian hookup drawings 1. p&id symbols and diagrams i like the world of instrumentation. smartplant (intools) engineering software.
The ISA Standards Committee on Instrument Loop Diagrams operates within the ISA Standards start-up, operation, maintenance, and mod-ification of instrumentation systems. Assist understanding. This standard will assist the understanding of instrument loop dia-.
Hook-up Process & Instrumentation compliance with DIN/ISA/UNI standards. or an instrument loop on the drawing and allows to Standard Technical Specification for Instrumentation.
Participation in the ISA standards-making process by an individual in no way in a suitable specification, data sheet, loop diagram, installation/wiring drawing.
For an older installation, the plant documentation may only exist as a series of paper standards address control and field instrumentation documentation, as well as other .. Piping and Instrumentation Diagram – Drawing that shows the.
hook up for instrument Hook-up Diagram Hook-up Diagram for Pressure Gauge Instrument Hook Up Instrument Hook Up Diagram instrument hook up diagrams isa standards instrument hook up drawing instrument hook up drawing autocad instrument hook up drawing dwg instrument hook up drawing pdf Instrumentation Tools assists you a complete guide which.
information needed for installation, checkout, start-up and maintenance. The ISA Standards Committee on Instrument Loop Diagrams operates within the ISA .
Ts - instrument in the isa standards committee on the instrumentation - phase iii: autocad. Line diagrams p id and pneumatic hookup diagram o input required list. Hook-Ups with or industrial diagram; instrument hook up diagrams cable schedules, and p .
PIPING AND INSTRUMENTATION DIAGRAMS (P&ID) (PROJECT STANDARDS AND SPECIFICATIONS) TABLE OF CONTENT SCOPE 2 REFERENCES 2 ISA (THE INTERNATIONAL SOCIETY OF AUTOMATION) Logic and Computer Systems "Ed.," - S "Instrument Loop Diagrams Ed., " - S "Graphic Symbols for Process Displays 1st. Ed., " KLM Technology .
Tag: instrument hook up diagrams isa standards. Instrument Hook Up Diagram is also called Installation drawing, specifies the scope of work between Mechanical and Instrumentation departments. It is a detailed drawing showing typical installation of an instrument.
An ounce in North Carolina is the same as an ounce in Nebraska, and you can hook up almost any kind of stereo component from any electronics store. How Your Company Can Take Advantage of ISA's Standards. Buy ISA standards and train your employees to follow it. Help set a standard. ISA's committees are eager for help.


Alice Peterson needlepoint kits are made in the USA! Kit includes 100% cotton #14 mesh canvas, embroidery floss, needle & instructions. Cording and backing not included. The use of embroidery floss gives a fine, smooth finish to your project. Hydrangea measures 14′ x 14′ and is suitable for framing or as a pillow top.


Djarum Mild Fliter 10/12 is a smoke that may be on the mild side but make no mistake that it is seriously loaded with rich and delicious taste. This little Kretek cigarillo has clove mixed into the tobacco to give it that unique taste known the world over by smokers everywhere. Buy them now!
I was introduced to Djarum Milds and they are very pleasant and mild for someone who does not smoke a lot. They re very smooth and satisfying.


text:
Ingo Schwichtenberg ( - ) est l'un des membres fondateurs du groupe allemand de power metal Helloween. Il est resté célèbre pour son jeu de batterie énergique.

Helloween
Avec Kai Hansen au chant et à la guitare, Michael Weikath à la guitare et Markus Grosskopf à la basse, Ingo est un des membres du line-up original d'Helloween.

Les autres membres du groupe lui avaient donné le surnom de « Mister Smile » ( Sourire), parce qu'il était rare de ne pas voir un sourire sur son visage et Ingo avait toujours un sourire sur les photos studios d'Helloween.

Ingo Schwichtenberg est renvoyé du groupe en 1993 lors de la tournée qui a suivi la sortie de l'album Chameleon. La raison invoquée est sa dépendance à l'alcool et aux drogues (plus particulièrement la cocaïne et le haschich). Ingo souffrait également de schizophrénie, et son refus de prendre ses médicaments générait des scènes gênantes comme le jour où il eut des sanglots incontrôlables qui l'empêchèrent de monter sur scène. Ingo était apparemment peu satisfait de la direction musicale prise par le groupe, en particulier sur la chanson Windmill de l'album Chameleon. D'après Michael Weikath, il l'avait renommée Shitmill.

Après son remplacement dans le groupe par Uli Kusch, Ingo s'enfonça davantage dans sa schizophrénie et se suicida le  en sautant sous une rame de métro.

Hommages
Son ami Kai Hansen lui a dédié la chanson Afterlife sur l'album Land of the Free de Gamma Ray. De la même manière, Michael Kiske lui rend hommage dans la chanson Always, de son premier album solo Instant Clarity.

Discographie
Avec Helloween
 Helloween (1985)
 Walls of Jericho (1985)
 Keeper of the Seven Keys Part 1 (1987)
 Keeper of the Seven Keys Part 2 (1988)
 Pink Bubbles Go Ape (1991)
 Chameleon (1993)

Avec Doc Eisenhauer
 Alles Im Lack (1992) - Chanson Pharao

Notes et références

Voir aussi
 Liste de batteurs de heavy metal

Liens externes

 Ingo-memory-page - un site dédié à la mémoire de Ingo Schwichtenberg
 Official Helloween site

Batteur de power metal
Batteur allemand de heavy metal
Naissance en mai 1965
Naissance à Hambourg
Décès en mars 1995
Décès à Hambourg
Décès à 29 ans
Musicien suicidé
Suicide en Allemagne
Suicide par précipitation en Allemagne
Personnalité ayant souffert de schizophrénie

redpajama_set_name: RedPajamaWikipedia


What is Literature Online Premium?
As literary studies grows increasingly interdisciplinary and with researchers needing to explore beyond the boundaries of traditional sources, Black Writing offers unprecedented opportunities to improve research with the inclusion of rare and ephemeral voices.
Analyse the earliest expressions of Black writers from influential periodicals such as The Afro-American up to the present day.