BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Guillaume Chapuy

Guillaume Chapuy appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COmath.PRmath-phmath.MPmath.ACmath.AGmath.GRmath.QAmath.RT

Catalog footprint

What is connected

21works
9topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

21 published item(s)

preprint2022arXiv

Non-orientable branched coverings, $b$-Hurwitz numbers, and positivity for multiparametric Jack expansions

We introduce a one-parameter deformation of the 2-Toda tau-function of (weighted) Hurwitz numbers, obtained by deforming Schur functions into Jack symmetric functions. We show that its coefficients are polynomials in the deformation parameter $b$ with nonnegative integer coefficients. These coefficients count generalized branched coverings of the sphere by an arbitrary surface, orientable or not, with an appropriate $b$-weighting that "measures" in some sense their non-orientability. Notable special cases include non-orientable dessins d'enfants for which we prove the most general result so far towards the Matching-Jack conjecture and the "$b$-conjecture" of Goulden and Jackson from 1996, expansions of the $β$-ensemble matrix model, deformations of the HCIZ integral, and $b$-Hurwitz numbers that we introduce here and that are $b$-deformations of classical (single or double) Hurwitz numbers obtained for $b=0$. A key role in our proof is played by a combinatorial model of non-orientable constellations equipped with a suitable $b$-weighting, whose partition function satisfies an infinite set of PDEs. These PDEs have two definitions, one given by Lax equations, the other one following an explicit combinatorial decomposition.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Topological recursion for Orlov-Scherbin tau functions, and constellations with internal faces

We study the correlators $W_{g,n}$ arising from Orlov-Scherbin 2-Toda tau functions with rational content-weight $G(z)$, at arbitrary values of the two sets of time parameters. Combinatorially, they correspond to generating functions of weighted Hurwitz numbers and $(m,r)$-factorisations of permutations. When the weight function is polynomial, they are generating functions of constellations on surfaces in which two full sets of degrees (black/white) are entirely controlled, and in which internal faces are allowed in addition to boundaries. We give the spectral curve (the "disk" function $W_{0,1}$, and the "cylinder" function $W_{0,2}$) for this model, generalising Eynard's solution of the 2-matrix model which corresponds to $G(z)=1+z$, by the addition of arbitrarily many free parameters. Our method relies both on the Albenque-Bouttier combinatorial proof of Eynard's result by slice decompositions, which is strong enough to handle the polynomial case, and on algebraic arguments. Building on this, we establish the topological recursion (TR) for the model. Our proof relies on the fact that TR is already known at time zero (or, combinatorially, when the underlying graphs have only boundaries, and no internal faces) by work of Bychkov-Dunin-Barkowski-Kazarian-Shadrin (or Alexandrov-Chapuy-Eynard-Harnad for the polynomial case), and on the general idea of deformation of spectral curves due to Eynard and Orantin, which we make explicit in this case. As a result of TR, we obtain strong structure results for all fixed-genus generating functions.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Counting chains in the noncrossing partition lattice via the W-Laplacian

We give an elementary, case-free, Coxeter-theoretic derivation of the formula $h^nn!/|W|$ for the number of maximal chains in the noncrossing partition lattice $NC(W)$ of a real reflection group $W$. Our proof proceeds by comparing the Deligne-Reading recursion with a parabolic recursion for the characteristic polynomial of the $W$-Laplacian matrix considered in our previous work. We further discuss the consequences of this formula for the geometric group theory of spherical and affine Artin groups.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

A bijection for rooted maps on general surfaces

We extend the Marcus-Schaeffer bijection between orientable rooted bipartite quadrangulations (equivalently: rooted maps) and orientable labeled one-face maps to the case of all surfaces, that is orientable and non-orientable 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 $\frac{5(h-1)}{2}$ for both orientable and non-orientable 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 Marcus-Schaeffer 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ørn-Budd bijections to the general setting of all surfaces. Our construction opens the way to the study of Brownian surfaces for any compact 2-dimensional manifold.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Packing triangles in weighted graphs

Tuza conjectured that for every graph $G$, the maximum size $ν$ of a set of edge-disjoint triangles and minimum size $τ$ of a set of edges meeting all triangles satisfy $τ\leq 2ν$. 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 $τ\leq 2ν^*$ (where $ν^*$ is the fractional version of $ν$), and asked if this is tight. We prove that $τ\leq 2ν^*-\frac{1}{\sqrt{6}}\sqrt{ν^*}$ and show that this bound is essentially best possible.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Counting factorizations of Coxeter elements into products of reflections

In this paper, we count factorizations of Coxeter elements in 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, J. Tits and D. Zagier in the real case and to D. Bessis in the complex case. For the symmetric group, our formula specializes to a formula of D. M. Jackson.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Simple recurrence formulas to count maps on orientable surfaces

We establish a simple recurrence formula for the number $Q_g^n$ of rooted orientable maps counted by edges and genus. We also give a weighted variant for the generating polynomial $Q_g^n(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 $M_g^{i,j}$ that count maps by genus, vertices, and faces. These formulas give by far the fastest known way of computing these numbers, or the fixed-genus generating functions, especially for large $g$. In the very particular case of one-face maps, we recover the Harer-Zagier 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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The asymptotic number of $12..d$-Avoiding Words with $r$ occurrences of each letter $1,2, ..., n$

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 $A_{d,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 $A_{d,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 $\sqrt{n}$). This relies on asymptotic estimates for the Kotska numbers $K_{λ,r^n}$ when $λ$ has a fixed number of parts. Contrarily to the case $r=1$ where these numbers are given by the hook-length formula, we don't have closed form expressions here, so to get our asymptotic estimates we rely on more delicate computations, via the Jacobi-Trudi identity and saddle-point estimates.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A simple model of trees for unicellular maps

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. 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, the Lehman-Walsh formula and the Goupil-Schaeffer formula. We also discuss several applications of our construction: we obtain a new proof of an identity related to covered maps due to Bernardi and the first author, and thanks to previous work of the second author, we give a new expression for Stanley character polynomials, which evaluate irreducible characters of the symmetric group. Finally, we show that our techniques apply partially to unicellular 3-constellations and to related objects that we call quasi-constellations.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A note on a Cayley graph of S_n

Recently in graph theory several authors have studied the spectrum of the Cayley graph of the symmetric group S_n generated by the transpositions (1, i) for 2 <= i <= n. Several conjectures were made and partial results were obtained. The purpose of this note is to point out that, as mentioned also by P. Renteln, this problem is actually already solved in another context. Indeed it is equivalent to studying the spectrum of so-called Jucys-Murphy elements in the algebra of the symmetric group, which is well understood. The aforementioned conjectures are direct consequences of the existing theory. We also present a related result from P. Biane, giving an asymptotic description of this spectrum. We insist on the fact that this note does not contain any new results, but has only been written to convey the information from the algebraic combinatorics community to graph theorists.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A note on the diameter of transportation polytopes with prescribed source degrees

Brightwell, van den Heuvel and Stougie proved that the diameter of an $m \times n$ transportation polytope is at most $8(m+n-2)$, a factor of eight away from the Hirsch Conjecture. This bound was improved to $3(m+n-1)$ by Hurkens. We investigate diameters for certain classes of transportation polytopes. Note: After the completion of this note, we discovered that the class of transportation polytopes studied in this note was already considered in Michel L. Balinski. On two special classes of transportation polytopes. Math. Programming Stud., 1:43-58, 1974. Michel L. Balinski and Fred J. Rispoli. Signature classes of transportation polytopes. Mathematical Programming, 60(2, Ser. A):127-144, 1993. These papers contain both refinements of our results and generalizations to more general classes of transportation problems. In view of these papers, this note will not be submitted for publication.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Tamari lattices and parking functions: proof of a conjecture of F. Bergeron

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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A bijection for covered maps, or a shortcut between Harer-Zagier's and Jackson's formulas

We consider maps on orientable surfaces. A map is called \emph{unicellular} if it has a single face. A \emph{covered map} is a map (of genus $g$) with a marked unicellular spanning submap (which 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, covered maps are maps with a marked spanning tree and our bijection specializes into a construction obtained by the first author in \cite{OB:boisees}. Covered maps can also be seen as \emph{shuffles} of two unicellular maps (one representing the unicellular submap, the other representing the dual unicellular submap). Thus, our bijection gives a correspondence between shuffles of unicellular maps, and pairs made of a plane tree and a unicellular bipartite map. In terms of counting, this establishes the equivalence between a formula due to Harer and Zagier for general unicellular maps, and a formula due to Jackson for bipartite unicellular maps. We also show that the bijection of Bouttier, Di Francesco and Guitter \cite{BDFG:mobiles} (which generalizes a previous bijection by Schaeffer \cite{Schaeffer:these}) between bipartite maps and so-called well-labelled mobiles can be obtained as a special case of our bijection.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A new combinatorial identity for unicellular maps, via a direct bijective approach

A unicellular map, or one-face map, is a graph embedded in an orientable surface such that its complement is a topological disk. In this paper, we give a new viewpoint to the structure of these objects, by describing a decomposition of any unicellular map into a unicellular map of smaller genus. This gives a new combinatorial identity for the number $ε_g(n)$ of unicellular maps of size $n$ and genus $g$. Contrarily to the Harer-Zagier recurrence formula, this identity is recursive in only one parameter (the genus). Iterating the construction gives an explicit bijection between unicellular maps and plane trees with distinguished vertices, which gives a combinatorial explanation (and proof) of the fact that $ε_g(n)$ is the product of the $n$-th Catalan number by a polynomial in $n$. The combinatorial interpretation also gives a new and simple formula for this polynomial. Variants of the problem are considered, like bipartite unicellular maps, or unicellular maps with cubic vertices only.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Asymptotic enumeration and limit laws for graphs of fixed genus

It is shown that the number of labelled graphs with n vertices that can be embedded in the orientable surface S_g of genus g grows asymptotically like $c^{(g)}n^{5(g-1)/2-1}γ^n n!$ where $c^{(g)}>0$, and $γ\approx 27.23$ is the exponential growth rate of planar graphs. This generalizes the result for the planar case g=0, obtained by Gimenez 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 S_g has a unique 2-connected component of linear size with high probability.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Counting unicellular maps on non-orientable surfaces

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 present a bijective link between unicellular maps on a non-orientable surface and 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 unicellular maps of fixed topology. In particular, we give exact formulas for the precubic case (all vertices of degree 1 or 3), and asymptotic formulas for the general case, when the number of edges goes to infinity. Our strategy is inspired by recent results obtained by the second author for the orientable case, but significant novelties are introduced: in particular we construct an involution which, in some sense, "averages" the effects of non-orientability.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

The structure of unicellular maps, and a connection between maps of positive genus and planar labelled trees

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. The bijection applies as well to the case of labelled unicellular maps, which are related to all rooted maps by Marcus and Schaeffer's bijection. This gives an immediate derivation of the asymptotic number of unicellular maps of given genus, and a simple bijective proof of a formula of Lehman and Walsh on the number of triangulations with one vertex. From the labelled case, we deduce an expression of the asymptotic number of maps of genus g with n edges involving the ISE random measure, and an explicit characterization of the limiting profile and radius of random bipartite quadrangulations of genus g in terms of the ISE.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

A bijection for rooted maps on orientable surfaces

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.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

A Complete Grammar for Decomposing a Family of Graphs into 3-connected Components

Tutte has described in the book "Connectivity in graphs" a canonical decomposition of any graph into 3-connected components. In this article we translate (using the language of symbolic combinatorics) Tutte's decomposition into a general grammar expressing any family of graphs (with some stability conditions) in terms of the 3-connected subfamily. A key ingredient we use is an extension of the so-called dissymmetry theorem, which yields negative signs in the grammar. As a main application we recover in a purely combinatorial way the analytic expression found by Giménez and Noy for the series counting labelled planar graphs (such an expression is crucial to do asymptotic enumeration and to obtain limit laws of various parameters on random planar graphs). Besides the grammar, an important ingredient of our method is a recent bijective construction of planar maps by Bouttier, Di Francesco and Guitter.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Asymptotic enumeration of constellations and related families of maps on orientable surfaces

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. Our proofs rely on the generalisation to orientable surfaces of the Bouttier-Di Francesco-Guitter bijection, and on generating series methods. We 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 Gao.

0 citations0 reviewsNo code linkedOpen access