Page web de Guillaume Chapuy.

LIAFA - UMR 7089 CNRS
Bâtiment Sophie Germain
Bureau 438 (tél: +33 1 57 27 92 49)

Adresse postale:
CNRS UMR 7089, Université Paris Diderot - Paris 7, Case 7014
75205 Paris Cedex 13
France

Email: mylastname(at)liafa.univ-paris-diderot.fr

Depuis Octobre 2010, je suis chargé de recherche au CNRS, affecté au LIAFA. Auparavant, j'ai effectué ma thèse au Laboratoire d'Informatique de l'École Polytechnique, sous la direction de Gilles Schaeffer, puis un an de postdoc au département de maths de l'université Simon Fraser de Vancouver (Canada).

Je travaille principalement dans le domaine de la combinatoire énumérative, et de l'analyse probabiliste de structures discrètes. Je m'intéresse en particulier aux cartes, qui sont des graphes plongés sur des surfaces. Mon travail concerne l'énumération exacte et asymptotique de ces objets, et l'analyse des grandes cartes aléatoires de genre fixé.

Preprints:

Counting factorizations of Coxeter elements into products of reflections (abstract) In this paper, we count factorizations of Coxeter elements in irreducible well-generated 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.
- (arxiv)
The representation of the symmetric group on m-Tamari intervals. (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.
with Mireille Bousquet-Mélou and Louis-François Préville-Ratelle.
- to appear in Advances in Mathematics. (arxiv)
- a short version also appeared in the proceedings of FPSAC 2012 (short)
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 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.
with Valentin Féray and Éric Fusy.
- submitted (arxiv)
- a short version also appeared in the proceedings of FPSAC 2012 (short)
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 2-connected and 3-connected embedded (maps) and unembedded planar graphs.
with Éric Fusy, Omer Giménez, and Marc Noy.
- submitted (arxiv)
- a short version was presented in the conference AofA 2010

Published papers:

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 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.
with Mireille Bousquet-Mé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 degree-restricted.
- Advances in Applied Mathematics, 47(4):874-893 (2011), 20 pages. (pdf file)
- a short version also appeared in the proceedings of FPSAC 2009 ("best student paper award") (short)
A bijection for covered maps, or a shortcut between Harer-Zagier'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. 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.
with Olivier Bernardi.
- Journal of Combinatorial Theory, Series A, 118(6):1718-1748 (2011), 31 pages. (pdf file)
- a short version with less enumerative results also appeared in the proceedings of the conference TGGT 2008 (short)
Counting unicellular maps on non-orientable 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 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.
with Olivier Bernardi.
- Advances in Applied Mathematics, 47(2):259-275(2011), 17 pages. (pdf file)
- a short version also appeared in the proceedings of FPSAC 2010 (short)
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(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.
with Éric Fusy, Omer Giménez, Bojan Mohar, and Marc Noy.
- Journal of Combinatorial Theory, Series A, 118(3):748-777 (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 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.
- Probability Theory and Related Fields 147(3):415-447 (2010), 33 pages. (pdf file)
A complete grammar for decomposing a family of graphs into 3-connected 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 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.
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: 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.
- Combinatorics, Probability, and Computing 18(04):477-516 (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)
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(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)
with Michel Marcus and Gilles Schaeffer.
- SIAM Journal on Discrete Mathematics, 23(3):1587-1611 (2009), 25 pages. (pdf file)
Random permutations and their discrepancy process. (abstract) My first paper...
- proceedings of the conference AofA 2007

Manuscripts:

Tamari lattices and parking functions: proof of a conjecture of F. Bergeron (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.
with Mireille Bousquet-Mélou and Louis-François Préville-Ratelle
- manuscript (arxiv) This was never submitted since soon after finishing this one we wrote our other paper "The representation of the symmetric group..." that generalizes the results from the dimension to the whole character of the representation (see above).
Packing triangles in weighted graphs (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.
with Matt DeVos, Jessica McDonald, Bojan Mohar, and Diego Scheide.
- submitted. (arxiv)

Misc.

I am the coordinator of the project Cartaplus, funded by the ANR.
Since 2011, I teach (about 15-20 hours a year) in the Combinatorics course of the M2 program MPRI.
I have defended my PhD thesis in June 2009.
Combinatoire bijective des cartes de genre supérieur (in French)
and the slides (in French) of my defense. (prix de thèse de l'École Polytechnique 2010).