Articles and preprints:

• The vertical profile of embedded trees (arxiv)
  with Mireille Bousquet-Mélou.
  submitted.
  
  (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 i-1 (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_0-1}} \prod_{l\le i\le r \atop i\not = 0}{{n_{i-1}+n_{i+1}-1} \choose {n_i-1}}, $$ with n_{l-1}=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.
• On the diameter of random planar graphs (arxiv)
  with Éric Fusy, Omer Giménez, and Marc Noy.
  sumbitted.
  (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 2-connected and 3-connected embedded (maps) and unembedded planar graphs.
• The representation of the symmetric group on m-Tamari intervals (arxiv)
  with Mireille Bousquet-Mélou and Louis-François Préville-Ratelle.
  submitted (extended abstract will appear in FPSAC'12).
  
  (abstract)

  An m-ballot 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 m-Tamari 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 m-Tamari 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 m-Tamari intervals of size n, is found to be $$ (m+1)^n(mn+1)^{n-2}. $$ 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 m-Tamari 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 non-standard: 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.
• A simple model of trees for unicellular maps (arxiv)
  with Valentin Féray and Éric Fusy.
  extended abstract in FPSAC'12.
  
  (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 permutation-like 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 Harer-Zagier recurrence formula, or the Lehman-Walsh/Goupil-Schaeffer 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.
• Tamari lattices and parking functions: proof of a conjecture of F. Bergeron (arxiv)
  with Mireille Bousquet-Mélou and Louis-François Préville-Ratelle.
  manuscript: will not be submitted.
  
  (abstract)

  An m-ballot 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 m-Tamari 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 coinvariant spaces. He conjectured several intriguing formulas dealing with the enumeration of intervals in this lattice. One of them states that the number of intervals in T_n^(m) is $$ \frac {m+1}{n(mn+1)} {(m+1)^2 n+m\choose n-1}. $$ This conjecture was proved recently, but in a non-bijective way, while its form strongly suggests a connection with plane trees. Here, we prove another conjecture of Bergeron, which deals with the number of labelled, intervals. 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. We prove that the number of labelled intervals in T_n^(m) is $$ {(m+1)^n(mn+1)^{n-2}}. $$ The form of these numbers suggests a connection with parking functions, but our proof is non-bijective. It is based on a recursive description of intervals, which translates into a functional equation satisfied by the associated generating function. This equation involves a derivative and a divided difference, taken with respect to two additional variables. Solving this equation is the hardest part of the paper. Finding a bijective proof remains an open problem.
  NOTE: This manuscript is superseded by the paper ``The representation of the symmetric group on m-Tamari-intervals'' above.
• A new combinatorial identity for unicellular maps, via a direct bijective approach. (pdf file)
  Advances in Applied Mathematics, 47(4):874-893 (2011), 20 pages.
  
  (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 degree-restricted.
• Packing triangles in weighted graphs (arxiv)
  with Matt DeVos, Jessica McDonald, Bojan Mohar, and Diego Scheide.
  submitted.
  
  (abstract)

  Tuza conjectured that for every graph G, the maximum size {\nu} of a set of edge-disjoint triangles and minimum size {\tau} of a set of edges meeting all triangles, satisfy {\tau} at most 2{\nu}. We consider an edge-weighted 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.
• A bijection for covered maps, or a shortcut between Harer-Zagier's and Jackson's formulas. (pdf file)
  with Olivier Bernardi.
  Journal of Combinatorial Theory, Series A, 118(6):1718-1748 (2011), 31 pages.
  (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. tree-rooted maps) and our bijection specializes into a construction obtained by the first author. A strong connection subsists between covered maps and tree-rooted maps in genus 1 (because a covered map is either a tree-rooted map or the dual of a tree-rooted map) and we thereby obtain a bijective explanation of a formula by Lehman and Walsh on the number of tree-rooted 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 so-called well-labelled mobiles can be described as a special case of our bijection.
• Counting unicellular maps on non-orientable surfaces. (pdf file)
  with Olivier Bernardi.
  Advances in Applied Mathematics, 47(2):259-275(2011), 17 pages.
  (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 non-orientable 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 non-orientable 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 non-orientability.
• Asymptotic enumeration and limit laws for graphs of fixed genus. (pdf file)
  with Éric Fusy, Omer Giménez, Bojan Mohar, and Marc Noy.
  Journal of Combinatorial Theory, Series A, 118(3):748-777 (2011), 30 pages.
  (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(g-1)/2-1}\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 non-orientable 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 2-connected component of linear size with high probability.
• The structure of unicellular maps, and a connection between maps of positive genus and planar labelled trees. (pdf file)
  Probability Theory and Related Fields 147(3):415-447 (2010), 33 pages.
  (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 fixed-genus large-size 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.
• A complete grammar for decomposing a family of graphs into 3-connected components. (pdf file)
  with Éric Fusy, Mihyun Kang, and Bilyana Shoilekova.
  Electronic Journal of Combinatorics 15:R148(2008), 39 pages.
  (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 3-connected 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 [Gimenez-Noy]); 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.
• Asymptotic enumeration of constellations and related families of maps on orientable surfaces. (pdf file)
  Combinatorics, Probability, and Computing 18(04):477-516 (2009), 40 pages.
  (abstract)

  We perform the asymptotic enumeration of two classes of rooted maps on orientable surfaces of genus g: m-hypermaps and m-constellations. 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 m-hypermaps and m-constellations --- 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.
• A bijection for rooted maps on orientable surfaces. (pdf file)
  with Michel Marcus and Gilles Schaeffer.
  SIAM Journal on Discrete Mathematics, 23(3):1587-1611 (2009), 25 pages.
  (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(g-1) 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).

Conference Proceedings:

• (*) Counting unicellular maps on non-orientable surfaces. (pdf file)
  with Olivier Bernardi.
  FPSAC 2010, 12 pages.
  (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 non-orientable 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 non-orientable 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 non-orientability.
• (*) On the diameter of random planar graphs. (pdf file)
  with Éric Fusy, Omer Giménez, and Marc Noy.
  Analysis of Algorithms 2010, 14 pages.
  (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 2-connected and 3-connected embedded (maps) and unembedded planar graphs.
• (*) A new combinatorial identity for unicellular maps, via a direct bijective approach. (pdf file)
  FPSAC'09: Formal Power Series and Algebraic Combinatorics 2009, Discrete Math. Theor. Comput. Sci. Proc., pp.289--300, 12 pages.
  (received the "Best student paper award")
  
  (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 degree-restricted.
• (*) Are even maps on surfaces likely to be bipartite ? (pdf file)
  MathInfo'08: Fifth Colloquium on Mathematics and Computer Science, Discrete Math. Theor. Comput. Sci. Proc., pp.363--374, 12 pages.
  This is a short version of the paper "Asymptotic enumeration of constellations..." above.
  (abstract)

  We show that even maps (maps with all faces of even degrees) of genus g are bipartite with probability tending to 1/2^{2g} when their size tends to infinity. Roughly, each fundamentnal cycle contributes a factor 1/2 to this probability. The results are based on the higher-genus version of the Bouttier, Di Francesco, Guitter bijection, and on generating series techniques.
• (*) A bijection for covered maps on orientable surfaces. (pdf file)
  with Olivier Bernardi.
  TGGT: The International Conference on Topological and Geometric Graph Theory, Electronic Notes in Discrete Math. 31: 63-68 (2008), 4 pages.
  
  (abstract)

  A covered map of genus g is a map of genus g with a spanning unicellular submap (by unicellular, we mean that the submap has only one border, but it can have genus lower than g). We compute the number of covered maps of genus g with n edges thanks to a bijection, that generalizes Bernardi's plane construction (EJC, Vol 14, 2007). From the special case of genus 1, and a duality argument, we obtain a bijective proof of a formula of Lehman and Walsh for the number of toroidal tree-rooted maps (maps with a spanning tree).
• Random permutations and their discrepancy process. (pdf file)
  AofA 07: 2007 Conference on Analysis of Algorithms, Discrete Math. Theor. Comput. Sci. Proc. pp. 415--426, 12 pages.
  
  (abstract)

  Let sigma be a random permutation chosen uniformly on S_n, and let Y_{p,q} = card {i<= p, sigma(i)<= q}. We show that a suitable normalisation of Y_{p,q} converges to a continuous random process (with bidimensional time) called the Bivariate tied-down Brownian Bridge. It is a centered Gaussian process with covariance: E[X_{s,t}X_{s',t'}]=(min(s,s')-ss')(min(t,t')-tt')

Thesis