Papers (published or in press)
For most papers below I provide a link to an arxiv or to a local version. These versions are close but not necessarily the same as the published versions, including the numbering of equations and theorems. In particular check the journal versions if you need to cite anything.

Connectivity in bridgeaddable graph classes: the McDiarmidStegerWelsh conjecture
(abstract)
A class of graphs is bridgeaddable if given a graph $G$ in the class, any
graph obtained by adding an edge between two connected components of $G$ is
also in the class. We prove a conjecture of McDiarmid, Steger, and Welsh, that
says that if $\mathcal{G}_n$ is any class of bridgeaddable graphs on $n$
vertices, and $G_n$ is taken uniformly at random from $\mathcal{G}_n$, then
$G_n$ is connected with probability at least $e^{\frac{1}{2}} + o(1)$, when
$n$ tends to infinity. This lower bound is asymptotically best possible since
it is reached for forests.
Previous results on this problem include the lower bound $e^{1}+o(1)$ proved
by McDiarmid, Steger and Welsh, and the successive improvements to
$e^{0.7983}+o(1)$ by Ballister, Bollob\'{a}s and Gerke, and to $e^{2/3}+o(1)$
in an unpublished draft of Norin. The bound $e^{\frac{1}{2}} + o(1)$ was
already known in the special case of bridgealterable classes, independently
proved by AddarioBerry, McDiarmid, and Reed, and by Kang and Panagiotou.
Our proof uses a "local double counting" strategy that may be of independent
interest, and that enables us to compare the size of two sets of combinatorial
objects by solving a related multivariate optimization problem. In our case,
the optimization problem deals with partition functions of trees weighted by a
supermultiplicative functional.
with Guillem Perarnau

Accepted for publication in the Journal of Combinatorial Theory, series B
(arxiv)

an extended abstract of this work was presented at the conference
SODA 2016.

On tessellations of random maps and the tgrecurrence
(abstract)
The number of $n$edge embedded graphs (rooted maps) on the $g$torus is
known to grow as $t_gn^{5(g1)/2}12^n$ when $g$ is fixed and $n$ tends to
infinity. The constants $t_g$ can be computed thanks to the nonlinear
"$t_g$recurrence", strongly related to the KP hierarchy and the double scaling
limit of the onematrix model. The combinatorial meaning of this simple
recurrence is still mysterious, and the purpose of this note is to point out an
interpretation, via a connection with random (Brownian) maps on surfaces.
Namely, we show that the $t_g$recurrence is equivalent, via known
combinatorial bijections, to the fact that $\mathbf{E}X_g^2=\frac{1}{3}$ for
any $g\geq 0$, where $X_g,1X_g$ are the masses of the nearestneighbour cells
surrounding two randomly chosen points in a Brownian map of genus $g$. This
raises the question (that we leave open) of giving an independent probabilistic
or combinatorial derivation of this second moment, which would then lead to a
concrete (combinatorial or probabilistic) interpretation of the
$t_g$recurrence. We also compute a similar moment in the case of three marked
points, for which a similar phenomenon occurs.
In fact, we conjecture that for any $g\geq 0$ and any $k\geq 2$, the masses
of the $k$ nearestneighbour cells induced by $k$ uniform points in the genus
$g$ Brownian map have the same law as a uniform $k$division of the unit
interval. We leave this question open even for $(g,k)=(0,2)$.

Accepted for publication in Probability Theory and Related Fields.
(arxiv)

Local convergence and stability of tight bridgeaddable graph classes
(abstract)
A class of graphs is bridgeaddable if given a graph G in the class, any graph obtained by adding an edge between two connected components of G is also in the class. The authors recently proved a conjecture of McDiarmid, Steger, and Welsh stating that if \G is bridgeaddable and Gn is a uniform nvertex graph from \G, then Gn is connected with probability at least (1+on(1))exp(−1/2). The constant exp(−1/2) is best possible since it is reached for the class of all forests.
In this paper we prove a form of uniqueness in this statement: if \G is a bridgeaddable class and the random graph Gn is connected with probability close to epx(−1/2), then Gn is asymptotically close to a uniform nvertex random forest in some local sense. For example, if the probability converges to epx(−1/2), then Gn converges in the sense of BenjaminiSchramm to the uniform infinite random forest. This result is reminiscent of socalled "stability results" in extremal graph theory, with the difference that here the stable extremum is not a graph but a graph class.
with Guillem Perarnau

Accepted for publication in the Canadian Journal of Mathematics.
(arxiv)

an extended abstract of this work was presented at the conference
RANDOM 2016.

Fermionic approach to weighted Hurwitz numbers and topological recursion
(abstract)
A fermionic representation is given for all the quantities entering in the generating function approach to weighted Hurwitz numbers and topological recursion. This includes: KP and 2D Toda τfunctions of hypergeometric type, which serve as generating functions for weighted single and double Hurwitz numbers; the Baker function, which is expanded in an adapted basis obtained by applying the same dressing transformation to all vacuum basis elements; the multipair correlators and the multicurrent correlators. Multiplicative and differential recursion relations are deduced for the adapted bases and their duals, and a ChristoffelDarboux type formula is derived for the pair correlator. The quantum and classical spectral curves linking this theory with the topological recursion programme are derived, as well as the generalized cut and join equations. The results are detailed for four special cases: the simple single and double Hurwitz numbers, the weakly monotone case, corresponding to signed enumeration of coverings, the strongly monotone case, corresponding to Belyi curves and the simplest version of quantum weighted Hurwitz numbers.
with Alexander Alexandrov, Bertrand Eynard, and John Harnad.

Communications in Mathematical Physics, 360, 777826 (2018).
(arxiv)

A bijection for rooted maps on general surfaces
(abstract)
We extend the MarcusSchaeffer bijection between orientable rooted bipartite quadrangulations (equivalently: rooted maps) and orientable labeled oneface maps to the case of all surfaces, that is orientable and nonorientable as well. This general construction requires new ideas and is more delicate than the special orientable case, but it carries the same information. In particular, it leads to a uniform combinatorial interpretation of the counting exponent 5(h−1)/2 for both orientable and nonorientable rooted connected maps of Euler characteristic 2−2h, and of the algebraicity of their generating functions, similar to the one previously obtained in the orientable case via the MarcusSchaeffer bijection. It also shows that the renormalization factor n^{1/4} for distances between vertices is universal for maps on all surfaces: the renormalized profile and radius in a uniform random pointed bipartite quadrangulation on any fixed surface converge in distribution when the size n tends to infinity. Finally, we extend the Miermont and AmbjörnBudd bijections to the general setting of all surfaces. Our construction opens the way to the study of Brownian surfaces for any compact 2dimensional manifold.
with Maciej Dołęga.

J. Combin. Theory Ser. A 145 (2017), 252–307.
(arxiv)

an extended abstract of this work (12 pages) appeared in the proceedings of the conference
FPSAC 2015.

Dimers on Rail Yard Graphs
(abstract)
We introduce a general model of dimer coverings of certain plane bipartite graphs, which we call rail yard graphs (RYG). The transfer matrices used to compute the partition function are shown to be isomorphic to certain operators arising in the socalled bosonfermion correspondence. This allows to reformulate the RYG dimer model as a Schur process, i.e. as a random sequence of integer partitions subject to some interlacing conditions.
Beyond the computation of the partition function, we provide an explicit expression for all correlation functions or, equivalently, for the inverse Kasteleyn matrix of the RYG dimer model. This expression, which is amenable to asymptotic analysis, follows from an exact combinatorial description of the operators localizing dimers in the transfermatrix formalism, and then a suitable application of Wick's theorem.
Plane partitions, domino tilings of the Aztec diamond, pyramid partitions, and steep tilings arise as particular cases of the RYG dimer model. For the Aztec diamond, we provide new derivations of the edgeprobability generating function, of the inverse Kasteleyn matrix and of the arctic circle theorem.
with Cédric Boutillier, Jérémie Bouttier, Sylvie Corteel and Sanjay Ramassamy.

Ann. Inst. Henri Poincaré D 4 (2017), 479539.
(arxiv)

Perfect sampling algorithms for Schur processes
(abstract)
We describe random generation algorithms for a large class of random combinatorial objects called Schur processes, which are sequences of random (integer) partitions subject to certain interlacing conditions. This class contains several fundamental combinatorial objects as special cases, such as plane partitions, tilings of Aztec diamonds, pyramid partitions and more generally steep domino tilings of the plane. Our algorithm, which is of polynomial complexity, is both exact (i.e. the output follows exactly the target probability law, which is either Boltzmann or uniform in our case), and entropy optimal (i.e. it reads a minimal number of random bits as an input).
The algorithm encompasses previous growth procedures for special Schur processes related to the primal and dual RSK algorithm, as well as the famous domino shuffling algorithm for domino tilings of the Aztec diamond. It can be easily adapted to deal with symmetric Schur processes and general Schur processes involving infinitely many parameters. It is more concrete and easier to implement than Borodin's algorithm, and it is entropy optimal.
At a technical level, it relies on unified bijective proofs of the different types of Cauchy and Littlewood identities for Schur functions, and on an adaptation of Fomin's growth diagram description of the RSK algorithm to that setting. Simulations performed with this algorithm suggest interesting limit shape phenomena for the corresponding tiling models, some of which are new.
with Dan Betea, Cédric Boutillier, Jérémie Bouttier, Sylvie Corteel, Mirjana Vuletić.

Markov Processes Relat. Fields 24, 381418 (2018)
(arxiv)

Laplacian matrices and spanning trees of tree graphs
(abstract)
If G is a strongly connected finite directed graph, the set TG of rooted directed spanning trees of G is naturally equipped with a structure of directed graph: there is a directed edge from any spanning tree to any other obtained by adding an outgoing edge at its root vertex and deleting the outgoing edge of the endpoint. Any Schrödinger operator on G, for example the Laplacian, can be lifted canonically to TG. We show that the determinant of such a lifted Schrödinger operator admits a remarkable factorization into a product of determinants of the restrictions of Schrödinger operators on subgraphs of G and we give a combinatorial description of the multiplicities using an exploration procedure of the graph. A similar factorization can be obtained from earlier ideas of C. Athaniasadis, but this leads to a different expression of the multiplicities, as signed sums on which the nonnegativity is not appearent. We also provide a description of the block structure associated with this factorization. As a simple illustration we reprove a formula of Bernardi enumerating spanning forests of the hypercube, that is closely related to the graph of spanning trees of a bouquet. Several combinatorial questions are left open, such as giving a bijective interpretation of the results.
with Philippe Biane

Ann. Fac. Sci. Toulouse Math. (6) 26 (2017), no. 2, 235–261.
(arxiv)

From Aztec diamonds to pyramids: steep tilings
(abstract)
We introduce a family of domino tilings that includes tilings of the Aztec diamond and pyramid partitions as special cases. These tilings live in a strip of ℤ2 of the form 1≤x−y≤2ℓ for some integer ℓ≥1, and are parametrized by a binary word w∈{+,−}2ℓ that encodes some periodicity conditions at infinity. Aztec diamond and pyramid partitions correspond respectively to w=(+−)ℓ and to the limit case w=+∞−∞. For each word w and for different types of boundary conditions, we obtain a nice product formula for the generating function of the associated tilings with respect to the number of flips, that admits a natural multivariate generalization. The main tools are a bijective correspondence with sequences of interlaced partitions and the vertex operator formalism (which we slightly extend in order to handle Littlewoodtype identities). In probabilistic terms our tilings map to Schur processes of different types (standard, Pfaffian and periodic). We also introduce a more general model that interpolates between domino tilings and plane partitions.
with Jérémie Bouttier and Sylvie Corteel.

Generating functions of bipartite maps on orientable surfaces
(abstract)
We compute, for each genus g≥0, the generating function Lg≡Lg(t;p1,p2,…) of (labelled) bipartite maps on the orientable surface of genus g, with control on all face degrees. We exhibit an explicit change of variables such that for each g, Lg is a rational function in the new variables, computable by an explicit recursion on the genus. The same holds for the generating function Fg of rooted bipartite maps. The form of the result is strikingly similar to the Goulden/Jackson/Vakil and Goulden/GuayPaquet/Novak formulas for the generating functions of classical and monotone Hurwitz numbers respectively, which suggests stronger links between these models. Our result complements recent results of Kazarian and Zograf, who studied the case where the number of faces is bounded, in the equivalent formalism of dessins d'enfants. Our proofs borrow some ideas from Eynard's "topological recursion" that he applied in particular to evenfaced maps (unconventionally called "bipartite maps" in his work). However, the present paper requires no previous knowledge of this topic and comes with elementary (complexanalysisfree) proofs written in the perspective of formal power series.
with Wenjie Fang

Electron. J. Combin. 23 (2016), no. 3, Paper 3.31, 37 pp.
(arxiv)

an extended abstract of this work (12 pages) appeared in the proceedings of the conference
FPSAC 2015.

The asymptotic number of 12..dAvoiding Words with r occurrences of each letter 1,2,...,n
(abstract)
Following Ekhad and Zeilberger (The Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, Dec 5 2014; see also arXiv:1412.2035), we study the asymptotics for large n of the number Ad,r(n) of words of length rn having r letters i for i=1..n, and having no increasing subsequence of length d. We prove an asymptotic formula conjectured by these authors, and we give explicitly the multiplicative constant appearing in the result, answering a question they asked. These two results should make the OEIS richer by 100+25=125 dollars.
In the case r=1 we recover Regev's result for permutations. Our proof goes as follows: expressing Ad,r(n) as a sum over tableaux via the RSK correspondence, we show that the only tableaux contributing to the sum are "almost" rectangular (in the scale n√). This relies on asymptotic estimates for the Kotska numbers Kλ,rn when λ has a fixed number of parts. Contrarily to the case r=1 where these numbers are given by the hooklength formula, we don't have closed form expressions here, so to get our asymptotic estimates we rely on more delicate computations, via the JacobiTrudi identity and saddlepoint estimates.

Manuscript (was never submitted)
(arxiv)

Simple recurrence formulas to count maps on orientable surfaces
(abstract)
We establish a simple recurrence formula for the number Qng of rooted orientable maps counted by edges and genus. We also give a weighted variant for the generating polynomial Qng(x) where x is a parameter taking the number of faces of the map into account, or equivalently a simple recurrence formula for the refined numbers Mi,jg that count maps by genus, vertices, and faces. These formulas give by far the fastest known way of computing these numbers, or the fixedgenus generating functions, especially for large g. In the very particular case of oneface maps, we recover the HarerZagier recurrence formula.
Our main formula is a consequence of the KP equation for the generating function of bipartite maps, coupled with a Tutte equation, and it was apparently unnoticed before. It is similar in look to the one discovered by Goulden and Jackson for triangulations, and indeed our method to go from the KP equation to the recurrence formula can be seen as a combinatorial simplification of Goulden and Jackson's approach (together with one additional combinatorial trick). All these formulas have a very combinatorial flavour, but finding a bijective interpretation is currently unsolved.
with Sean R. Carrell.

Journal of Combinatorial Theory, Series A, 133:58–75 (2015).
(arxiv)

a shorter version (with only the twoparameter recurrence formula) will also appear in the proceedings of the conference
FPSAC 2014.

a short
Maple worksheet containing our recurrences formulas and enabling you to compute map numbers or generating functions very quickly!

(related slides, in French)
(and English)

Counting factorizations of Coxeter elements into products of reflections
(abstract)
In this paper, we count factorizations of Coxeter elements in irreducible wellgenerated complex reflection groups into products of reflections. We obtain a simple product formula for the exponential generating function of such factorizations, which is expressed uniformly in terms of natural parameters of the group. In the case of factorizations of minimal length, we recover a formula due to P. Deligne in the real case and to D. Bessis in the complex case. For the symmetric group, our formula specializes to a formula of B. Shapiro, M. Shapiro and A. Vainshtein.
with Christian Stump.

The local limit of unicellular maps in high genus
(abstract)
We show that the local limit of unicellular maps whose genus is proportional to the number of edges is a supercritical geometric GaltonWatson tree conditioned to survive. The proof relies on enumeration results obtained via the recent bijection given by the second author together with Feray and Fusy.
with Omer Angel, Nicolas Curien, and Gourab Ray.

Electron. Commun. Probab. 18 (2013), no. 86, 8 pp.
(arxiv)

On the diameter of random planar graphs
(abstract)
We show that the diameter D(G_n) of a random (unembedded) labelled
connected planar graph with n
vertices is asymptotically almost surely of order $n^{1/4}$, in the
sense that there exists
a constant c>0 such that
$P(n^{1/4\epsilon}<D(G_n)<n^{1/4+\epsilon}))<
1\exp(n^{c\epsilon})$ for $\epsilon$ small enough and
$n$ large enough ($n> n_0(\epsilon)$). We prove similar statements
for rooted 2connected and 3connected embedded (maps) and unembedded
planar graphs.
with Éric Fusy, Omer Giménez, and Marc Noy.

Combinatorics, Probability and Computing, 24(01):145–178 (2015). Special Issue Honouring the Memory of Philippe Flajolet.
(arxiv)

a short version was presented in the conference
AofA 2010

(related slides)

The representation of the symmetric group on mTamari intervals.
(abstract)
An mballot path of size n is a path on the square grid consisting of
north and east unit steps, starting at (0,0), ending at (mn,n), and
never going below the line {x=my}. The set of these paths can be
equipped with a lattice structure, called the mTamari lattice and
denoted by T_n^{m}, which generalizes the usual Tamari lattice T_n
obtained when m=1. This lattice was introduced by F. Bergeron in
connection with the study of diagonal coinvariant spaces in three sets
of n variables. The representation of the symmetric group S_n on these
spaces is conjectured to be closely related to the natural
representation of S_n on (labelled) intervals of the mTamari lattice,
which we study in this paper. An interval [P,Q] of T_n^{m} is labelled
if the north steps of Q are labelled from 1 to n in such a way the
labels increase along any sequence of consecutive north steps. The
symmetric group S_n acts on labelled intervals of T_n^{m} by permutation
of the labels. We prove an explicit formula, conjectured by F. Bergeron
and the third author, for the character of the associated
representation of S_n. In particular, the dimension of the
representation, that is, the number of labelled mTamari intervals of
size n, is found to be $$ (m+1)^n(mn+1)^{n2}. $$ These results are new,
even when m=1. The form of these numbers suggests a connection with
parking functions, but our proof is not bijective. The starting point is
a recursive description of mTamari intervals. It yields an equation
for an associated generating function, which is a refined version of the
Frobenius series of the representation. The form of this equation is
highly nonstandard: it involves two additional variables x and y, a
derivative with respect to y and iterated divided differences with
respect to x. The hardest part of the proof consists in solving it, and
we develop original techniques to do so.
NOTE: some techniques used in this paper are common with our (unsubmitted)
manuscript ''Tamari lattices and parking functions: proof of a
conjecture of F. Bergeron'' below, which dealt only with the enumerative case. It may be a good introduction to our techniques.
with Mireille BousquetMélou and LouisFrançois PrévilleRatelle.

Advances in Mathematics, 247:309342 (2013).
(arxiv)

a short version also appeared in the proceedings of
FPSAC 2012
(short version)

(related slides)

A previous manuscript, entitled Tamari lattices and parking functions: proof of a conjecture of F. Bergeron and never submitted (since it was soon superseded by this one) is available there:
(previousmanuscriptarxiv).
It contains only the results on the dimension/enumeration, not the full representation, and it may be a more accessible, less technical, introduction to our method.

Packing triangles in weighted graphs
(abstract)
Tuza conjectured that for every graph G, the maximum size {\nu} of a set of
edgedisjoint triangles and minimum size {\tau} of a set of edges meeting all
triangles, satisfy {\tau} at most 2{\nu}. We consider an edgeweighted version
of this conjecture, which amounts to packing and covering triangles in
multigraphs. Several known results about the original problem are shown to be
true in this context, and some are improved. In particular, we answer a
question of Krivelevich who proved that {\tau} is at most 2{\nu}* (where {\nu}*
is the fractional version of {\nu}), and asked if this is tight. We prove that
{\tau} is at most 2{\nu}*sqrt({\nu}*)/4 and show that this bound is
essentially best possible.
with Matt DeVos, Jessica McDonald, Bojan Mohar, and Diego Scheide.

SIAM J. Discrete Math. 281 (2014), pp. 226239.
(arxiv)

A simple model of trees for unicellular maps
(abstract)
We consider unicellular maps, or polygon gluings, of fixed genus. A few years
ago the first author gave a recursive bijection transforming unicellular maps
into trees, explaining the presence of Catalan numbers in counting formulas for
these objects (see the paper "A new combinatorial identity..." below). In this paper, we give another bijection that explicitly
describes the "recursive part" of the first bijection. As a result we obtain a
very simple description of unicellular maps as pairs made by a plane tree and a
permutationlike structure. All the previously known formulas follow as an
immediate corollary or easy exercise, thus giving a bijective proof for each of
them, in a unified way. For some of these formulas, this is the first bijective
proof, e.g. the HarerZagier recurrence formula, or the
LehmanWalsh/GoupilSchaeffer formulas. Thanks to previous work of the second
author this also leads us to a new expression for Stanley character
polynomials, which evaluate irreducible characters of the symmetric group.
with Valentin Féray and
Éric Fusy.

The vertical profile of embedded trees.
(abstract)
Consider a rooted binary tree with n nodes. Assign with the root the abscissa
0, and with the left (resp. right) child of a node of abscissa i the abscissa
i1 (resp. i+1). We prove that the number of binary trees of size n having
exactly n_i nodes at abscissa i, for l =< i =< r (with n = sum_i n_i), is $$
\frac{n_0}{n_l n_r} {{n_{1}+n_1} \choose {n_01}} \prod_{l\le i\le r \atop
i\not = 0}{{n_{i1}+n_{i+1}1} \choose {n_i1}}, $$ with n_{l1}=n_{r+1}=0. The
sequence (n_l, ..., n_{1};n_0, ..., n_r) is called the vertical profile of the
tree. The vertical profile of a uniform random tree of size n is known to
converge, in a certain sense and after normalization, to a random mesure called
the integrated superbrownian excursion, which motivates our interest in the
profile. We prove similar looking formulas for other families of trees whose
nodes are embedded in Z. We also refine these formulas by taking into account
the number of nodes at abscissa j whose parent lies at abscissa i, and/or the
number of vertices at abscissa i having a prescribed number of children at
abscissa j, for all i and j. Our proofs are bijective.
with Mireille BousquetMélou.

Electronic Journal of Combinatorics, 19(3):P46 (2012), 61 pages.
(arxiv)

A new combinatorial identity for unicellular maps, via a direct bijective approach.
(abstract)
We perform the first bijective counting of unicellular maps of fixed
size and genus, by giving a bijective operation that relates
unicellular maps of given genus to unicellular maps of lower genus,
with distinguished vertices. This gives a new combinatorial identity
relating the number epsilon_g(n) of unicellular maps of size n and
genus g to the numbers epsilon_j(n), for j<g.
By iterating this construction, we show that all unicellular maps can
be obtained by successive gluings of vertices in a plane tree. In
particular, this is the first interpretation of the fact that the
number epsilon_g(n) is a product of a polynomial by a Catalan number.
Our method is completely constructive, since it enables to sample
(exhaustively or at random) unicellular maps of given genus and size,
and it adapts easily to several classes of unicellular maps, for
example bipartite, or degreerestricted.

A bijection for covered maps, or a shortcut between HarerZagier's and Jackson's formulas.
(abstract)
We consider maps on orientable surfaces. A map is unicellular if it has
a single face. A covered map is a map with a marked unicellular
spanning submap. For a map of genus g, the unicellular submap can have
any genus in 0,1,..., g. Our main result is a bijection between covered
maps with n edges and genus g and pairs made of a plane tree with n
edges and a unicellular bipartite map of genus g with n+1 edges.
In the planar case, the covered maps are maps with a marked spanning
tree (a.k.a. treerooted maps) and our bijection specializes into a
construction obtained by the first author. A strong connection subsists
between covered maps and treerooted maps in genus 1 (because a covered
map is either a treerooted map or the dual of a treerooted map) and we
thereby obtain a bijective explanation of a formula by Lehman and Walsh
on the number of treerooted maps of genus 1. A more surprising
byproduct of our bijection is an equivalence between an enumerative
formula by Harer and Zagier concerning unicellular maps of given genus
and a similar formula by Adrianov concerning bipartite unicellular maps
of given genus. The equivalence is obtained by observing that covered
maps can be seen as a shuffle of two unicellular maps, hence that our
bijection gives a relations between shuffles of unicellular maps and
bipartite unicellular maps.
We also show that the bijection of Bouttier, Di Francesco and Guitter
(which generalizes a famous bijection by Schaeffer) between bipartite
maps and socalled welllabelled mobiles can be described as a special
case of our bijection.
with Olivier Bernardi.

Counting unicellular maps on nonorientable surfaces.
(abstract)
A unicellular map is the embedding of a connected graph in a surface in
such a way that the complement of the graph is a topological disk. In
this paper we give a bijective operation that relates unicellular maps
on a nonorientable surface to unicellular maps of a lower topological
type, with distinguished vertices. From that we obtain a recurrence
equation that leads to (new) explicit counting formulas for
nonorientable precubic (all vertices of degree $1$ or $3$) unicellular
maps of fixed topology. We also determine asymptotic formulas for the
number of all unicellular maps of fixed topology, when the number of
edges goes to infinity.
Our strategy is inspired by recent results obtained for the orientable
case [Chapuy, PTRF, to appear], but significant novelties are
introduced: in particular we construct an involution which, in some
sense, "averages" the effects of nonorientability.
with Olivier Bernardi.

Asymptotic enumeration and limit laws for graphs of fixed genus.
(abstract)
It is shown that the number of labelled graphs with $n$ vertices that
can be embedded in the orientable surface $\mathbb{S}_g$ of genus
$g$ grows asymptotically like
$
c^{(g)}n^{5(g1)/21}\gamma^n n!
$,
where $c^{(g)} >0$, and $\gamma \approx 27.23$ is the exponential
growth rate of planar graphs. This generalizes the result for the
planar case $g=0$, obtained by Giménez and Noy.
An analogous result for nonorientable surfaces is obtained. In
addition, it is proved that several parameters of interest behave
asymptotically as in the planar case. It follows, in particular, that
a random graph embeddable in $\mathbb{S}_g$ has a unique
2connected component of linear size with high probability.
with Éric Fusy, Omer Giménez, Bojan Mohar, and Marc Noy.

Journal of Combinatorial Theory, Series A, 118(3):748777 (2011), 30 pages
(arxiv)

The structure of unicellular maps, and
a connection between maps of positive genus and planar labelled trees.
(abstract)
(NB: A refinement of the combinatorial part of this paper was given later in the paper A new combinatorial identity for unicellular maps... above. Still, the (asymptotic) bijection in this PTRF paper is all you need for fixedgenus largesize limits).
A unicellular map is a map which has only one face. We give a bijection
between a dominant subset of rooted unicellular maps of fixed genus and
a set
of rooted plane trees with distinguished vertices, which leads to an
easy asymptotic counting of unicellular maps of fixed genus. From the
labelled case, we obtain new connections between maps of positive genus
and the ISE random measure. For example, we obtain a description of the
limiting profile of bipartite quadrangulations of genus g in terms of
the ISE.

Probability Theory and Related Fields 147(3):415447 (2010), 33 pages.
(pdf file)

A complete grammar for
decomposing a family of graphs into 3connected
components.
(abstract)
In this article, we recover the results of Gimenez and Noy for the
generating series counting planar graphs, via a different method. This
is done thanks to a complete grammar, written in the language of
symbolic combinatorics, for the decomposition of a family of graphs
into 3connected components, and thanks to a bijective derivation of
the generating series counting labelled planar maps pointed in several
ways.
The main advantages of our method are: first, that all
the calculations are simple (we do not need the two difficult
integration steps as in [GimenezNoy]); second, that our grammar is
general and also applies to other families of labelled graphs, and,
hopefully, is a promising tool toward the enumeration of unlabelled
planar graphs.
with
Éric Fusy, Mihyun Kang, and Bilyana
Shoilekova.

Electronic Journal of Combinatorics 15:R148(2008), 39 pages.
(pdf
file)

Asymptotic enumeration of
constellations and related families of maps on orientable surfaces.
(abstract)
We perform the asymptotic enumeration of two
classes of rooted maps on orientable surfaces of
genus g: mhypermaps and mconstellations.
For m=2 they correspond respectively to maps with even face
degrees and bipartite maps. We obtain explicit asymptotic formulas for
the number of such maps with any finite set of allowed face degrees.
We also show that each of the 2g fondamental cycles of the
surface contributes a factor m between the numbers
of mhypermaps and mconstellations  for example,
large maps of genus g with even face degrees are bipartite
with probability tending to 1/2^{2g}.
A special case of our results implies former conjectures of Z. Gao.

Combinatorics, Probability, and Computing 18(04):477516 (2009), 40 pages
(pdf file)

a related, less general, conference paper Are even maps on surfaces likely to be bipartite?
appeared in the proceedings of
MathInfo'08. It presents the results in the even degree case.
(short version)

A bijection for rooted maps on orientable surfaces.
(abstract)
We use the Marcus and Schaeffer's bijection, that relates rooted maps on orientable surfaces to labelled unicellular
maps, to perform the asymptotic enumeration of rooted maps of given
genus. In particular, we derive in a combinatorial way
the exponent 5/2(g1) counting maps of genus g (a result already
obtained by Bender and Canfield by an extension of Tutte's method, or
by matrix integrals techniques)
with Michel Marcus and Gilles Schaeffer.

SIAM Journal on Discrete Mathematics, 23(3):15871611 (2009), 25 pages.
(pdf file)

Random permutations and their discrepancy process.
(abstract)
My first paper... Let σ be a random permutation chosen uniformly over the symmetric group Sn. We study a new "processvalued" statistic of σ, which appears in the domain of computational biology to construct tests of similarity between ordered lists of genes. More precisely, we consider the following "partial sums": Y(n)p,q = card{1 ≤i ≤p : σi ≤q } for 0≤p,q≤n We show that a suitable normalization of Y(n) converges weakly to a bivariate tied down brownian bridge on [0,1]2, i.e. a continuous centered gaussian process X∞s,t of covariance: E[X∞s,tX∞s',t'] = (min(s,s')ss')(min(t,t')tt')

DMTCS Proceedings, 2007 Conference on Analysis of Algorithms, AofA 07.
(pdf file)