Misc.

• Jointly with Marni Mishna we organise a new weekly seminar!
   
• This semester I am teaching MACM201: Introduction to Discrete Mathematics II. Students will find all the related material on the SFU webCT server.

Preprints

• Asymptotic enumeration and limit laws for graphs of fixed genus. (pdf file)
  with Éric Fusy, Omer Giménez, Bojan Mohar, and Marc Noy.
  submitted to the Journal of Combinatorial Theory, series A, 33 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.
• Counting unicellular maps on non-orientable surfaces. (pdf file)
  with Olivier Bernardi.
  accepted to 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.
• A bijection for covered maps, or a shortcut between Harer-Zagier's and Jackson's formulas. (pdf file)
  with Olivier Bernardi.
  submitted to the Journal of Combinatorial Theory, series A, 42 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.
  [note: the title of this paper has changed several times while it was in preparation, so if you are looking for a paper with "almost" the same title, it should be this one!]

Articles in Journals:

• The structure of unicellular maps, and a connection between maps of positive genus and planar labelled trees. (pdf file) or (already published on the website of the journal)
  Probability Theory and Related Fields (to appear), 33 pages.
  (abstract)
  

  (NB: a refinement of the combinatorial part of this paper is given in the FPSAC'09 paper below).
  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).

Articles in Conference Proceedings:

• A new combinatorial identity for unicellular maps, via a direct bijective approach. (pdf file) or (preliminary long version)
  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" from the conference program committee)
  
  (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 shorten 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)

  By a direct enumerative approach, we investigate the repartition of the 0's and 1's in a large random permutation matrix. We show that this repartition can be described by a bivariate stochastic process, the tied-down bivariate Brownian bridge.

Thesis