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.

Nonorientable branched coverings, bHurwitz numbers, and positivity for multiparametric Jack expansions
with Maciej Dołęga.
Advances in Mathematics, Volume 409, Part A, 2022, 108645.
[arxiv]
[doi link]
[more info]
We introduce a oneparameter deformation of the 2Toda taufunction 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 bweighting that "measures" in some sense their nonorientability. Notable special cases include nonorientable dessins d'enfants for which we prove the most general result so far towards the MatchingJack conjecture and the "bconjecture" of Goulden and Jackson from 1996, expansions of the βensemble matrix model, deformations of the HCIZ integral, and bHurwitz numbers that we introduce here and that are bdeformations of classical (single or double) Hurwitz numbers obtained for b=0. A key role in our proof is played by a combinatorial model of nonorientable constellations equipped with a suitable bweighting, 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.
Check also my recorded talk at LaBRI (talk in French but slides in English) or my talk at the ACOW online workshop.

Coxeter factorizations with generalized JucysMurphy weights and Matrix Tree theorems for reflection groups
with Theo Douvropoulos.
Proceedings of the London Mathematical Society (to appear).
[arxiv]
[more info]
We prove universal (casefree) formulas for the weighted enumeration of factorizations of Coxeter elements into products of reflections valid in any wellgenerated reflection group W, in terms of the spectrum of an associated operator, the WLaplacian. This covers in particular all finite Coxeter groups. The results of this paper include generalizations of the Matrix Tree and Matrix Forest theorems to reflection groups, and cover reduced (shortest length) as well as arbitrary length factorizations.
Our formulas are relative to a choice of weighting system that consists of n free scalar parameters and is defined in terms of a tower of parabolic subgroups. To study such systems we introduce (a class of) variants of the JucysMurphy elements for every group, from which we define a new notion of `tower equivalence' of virtual characters. A main technical point is to prove the tower equivalence between virtual characters naturally appearing in the problem, and exterior products of the reflection representation of W.
Finally we study how this WLaplacian matrix we introduce can be used in other problems in Coxeter combinatorics. We explain how it defines analogues of trees for W and how it relates them to Coxeter factorizations, we give new numerological identities between the Coxeter number of W and those of its parabolic subgroups, and finally, when W is a Weyl group, we produce a new, explicit formula for the volume of the corresponding root zonotope.
Check also Theo's cool slides about this work on his webpage.

bmonotone Hurwitz numbers: Virasoro constraints, BKP hierarchy, and O(N)BGW integral
with Valentin Bonzom and Maciej Dołęga.
International Mathematics Research Notices, 2022, rnac177.
[arxiv]
[doi link]
[more info]
We study a \(b\)deformation of monotone Hurwitz numbers, obtained by deforming
Schur functions into Jack symmetric functions. It is a special case of the
\(b\)deformed weighted Hurwitz numbers recently introduced by the last two
authors and has an interpretation in terms of generalized branched coverings of
the sphere by nonoriented surfaces. We give an evolution (cutandjoin) equation for this model and we derive, by
a method of independent interest, explicit Virasoro constraints from it, for
arbitrary values of the deformation parameter \(b\). We apply them to prove a
conjecture of F\'eray on Jack characters. We also provide a combinatorial model
of nonoriented monotone Hurwitz maps, which generalizes monotone transposition
factorizations. In the case \(b=1\) we show that the model obeys the BKP hierarchy of Kac and
Van de Leur. As a consequence of our analysis we prove a recent conjecture of
Oliveira and Novaes relating zonal polynomials with the dimensions of
irreducible representations of \(O(N)\). We also relate the model to an \(O(N)\)
version of the Br\'ezinGrossWitten integral, which we solve explicitly in
terms of Pfaffians in the case of even multiplicities.

Counting chains in the noncrossing partition lattice via the WLaplacian
with Theo Douvropoulos.
Journal of Algebra 602 (2022) 381404.
[arxiv]
[doi link]
[more info]
We give an elementary, casefree, Coxetertheoretic 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 DeligneReading 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.

On the number of coloured triangulations of dmanifolds
with Guillem Perarnau
Discrete & Computational Geometry 65 (2021), 601–617.
[arxiv]
[doi link]
[more info]
We give superexponential lower and upper bounds on the number of coloured ddimensional triangulations whose underlying space is a manifold, when the number of simplices goes to infinity and d≥3 is fixed. In the special case of dimension 3, the lower and upper bounds match up to exponential factors, and we show that there are \(2^{\Theta(n)}n^(n/6)\) coloured triangulations of 3manifolds with n tetrahedra. Our results also imply that random coloured triangulations of 3manifolds have a sublinear number of vertices.
Our upper bounds apply in particular to coloured dspheres for which they seem to be the best known bounds in any dimension d≥3, even though it is often conjectured that exponential bounds hold in this case.
We also ask a related question on regular edgecoloured graphs having the property that each 3coloured component is planar, which is of independent interest.

Weighted Hurwitz numbers and topological recursion
with Alexander Alexandrov, Bertrand Eynard, and John Harnad.
Communications in Mathematical Physics 375 (2020), 237–305.
[arxiv]
[doi link]
[more info]
The KP and 2D Toda taufunctions of hypergeometric type that serve as generating functions for weighted single and double Hurwitz numbers are related to the topological recursion programme. A graphical representation of such weighted Hurwitz numbers is given in terms of weighted constellations. The associated classical and quantum spectral spectral curves are derived, and these are interpreted combinatorially in terms of the graphical model. The pair correlators are given a finite ChristoffelDarboux representation and determinantal expressions are obtained for the multipair correlators. The genus expansion of the multicurrent correlators is shown to provide generating series for weighted Hurwitz numbers of fixed ramification profile lengths. The WKB series for the Baker function is derived and used to deduce the loop equations and the topological recursion relations.

Voronoi tessellations in the CRT and continuum random maps of finite excess
with Louigi AddarioBerry, Omer Angel,Éric Fusy, Christina Goldschmidt.
Proceedings of the 2018 Annual ACMSIAM Symposium on Discrete Algorithms
(SODA 2018)
[doi link]
[more info]
Given a large graph G and k agents on this graph, we consider the Voronoi tessellation induced by the graph distance. Each agent gets control of the portion of the graph that is closer to itself than to any other agent. We study the limit law of the vector Vor: = (V1/n, V2/n, …, Vk/n), whose i'th coordinate records the fraction of vertices of G controlled by the i'th agent, as n tends to infinity. We show that if G is a uniform random tree, and the agents are placed uniformly at random, the limit law of Vor is uniform on the (k – 1)dimensional simplex. In particular, when k = 2, the two agents each get a uniform random fraction of the territory. In fact, we prove the result directly on the Brownian continuum random tree (CRT), and we also prove the same result for a “higher genus” analogue of the CRT that we call the continuum random unicellular map, indexed by a genus parameter g ≥ 0. As a key step of independent interest, we study the case when G is a random planar embedded graph with a finite number of faces. The main idea of the proof is to show that Vor has the same distribution as another partition of mass Int: = (I1/n, I2/n, …, Ik/n) where Ij is the contour length separating the ith agent from the next one in clockwise order around the graph.
Check the
slides! (including a oneslide proof of the main result!).
The probability that a journal version of this paper appears decreases with time.

Connectivity in bridgeaddable graph classes: the McDiarmidStegerWelsh conjecture
with Guillem Perarnau
J. Combin. Theory Ser. B 136 (2019), 44–71.
[arxiv]
[doi link]
[extended abstract at SODA'16]
[more info]
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.

On tessellations of random maps and the tgrecurrence
Probab. Theory Related Fields 174 (2019), no. 12, 477–500.
[arxiv]
[doi link]
[more info]
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)\).

Local convergence and stability of tight bridgeaddable graph classes
with Guillem Perarnau
Canadian Journal of Mathematics , Volume 72 , Issue 3 , June 2020 , pp. 563  601.
[arxiv]
[doi link]
[extended abstract at RANDOM'16]
[more info]
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.

Fermionic approach to weighted Hurwitz numbers and topological recursion
with Alexander Alexandrov, Bertrand Eynard, and John Harnad.
Communications in Mathematical Physics, 360, 777826 (2018).
[arxiv]
[doi link]
[more info]
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.

A bijection for rooted maps on general surfaces
with Maciej Dołęga.
J. Combin. Theory Ser. A 145 (2017), 252–307.
[arxiv]
[doi link]
[more info]
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.
An extended abstract of this work (12 pages) appeared in the proceedings of the conference
FPSAC 2015.

Dimers on Rail Yard Graphs
with Cédric Boutillier, Jérémie Bouttier, Sylvie Corteel and Sanjay Ramassamy.
Ann. Inst. Henri Poincaré D 4 (2017), 479539.
[arxiv]
[doi link]
[more info]
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.

Perfect sampling algorithms for Schur processes
with Dan Betea, Cédric Boutillier, Jérémie Bouttier, Sylvie Corteel, Mirjana Vuletić.
Markov Processes Relat. Fields 24, 381418 (2018)
[arxiv]
[more info]
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.

Laplacian matrices and spanning trees of tree graphs
with Philippe Biane
Ann. Fac. Sci. Toulouse Math. (6) 26 (2017), no. 2, 235–261.
[arxiv]
[doi link]
[more info]
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.

From Aztec diamonds to pyramids: steep tilings
with Jérémie Bouttier and Sylvie Corteel.
Trans. Amer. Math. Soc. 369 (2017), no. 8, 5921–5959.
[arxiv]
[doi link]
[more info]
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.

Generating functions of bipartite maps on orientable surfaces
with Wenjie Fang
Electron. J. Combin. 23 (2016), no. 3, Paper 3.31, 37 pp.
[arxiv]
[doi link]
[more info]
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.
an extended abstract of this work (12 pages) appeared in the proceedings of the conference FSPAC 2015.

The asymptotic number of 12..dAvoiding Words with r occurrences of each letter 1,2,...,n
Manuscript (was never submitted)
[arxiv]
[more info]
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.

Simple recurrence formulas to count maps on orientable surfaces
with Sean R. Carrell.
Journal of Combinatorial Theory, Series A, 133:58–75 (2015).
[arxiv]
[doi link]
[more info]
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.
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

Counting factorizations of Coxeter elements into products of reflections
with Christian Stump.
Journal of the London Mathematical Society, 90 (3): 919939 (2014).
[arxiv]
[doi link]
[related slides]
[more info]
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.

The local limit of unicellular maps in high genus
with Omer Angel, Nicolas Curien, and Gourab Ray.
Electron. Commun. Probab. 18 (2013), 18.
[arxiv]
[doi link]
[more info]
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.

On the diameter of random 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]
[doi link]
[related slides]
[more info]
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.
A short version was presented in the conference
AofA 2010.

The representation of the symmetric group on mTamari intervals.
with Mireille BousquetMélou and LouisFrançois PrévilleRatelle.
Advances in Mathematics, 247:309342 (2013).
[arxiv]
[doi link]
[more info]
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.
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
with Matt DeVos, Jessica McDonald, Bojan Mohar, and Diego Scheide.
SIAM J. Discrete Math. 281 (2014), pp. 226239.
[arxiv]
[doi link]
[more info]
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.

A simple model of trees for unicellular maps
with Valentin Féray and
Éric Fusy.
Journal of Combinatorial Theory, Series A, 120(8):2064–2092 (2013), 29 pages.
[arxiv]
[doi link]
[related slides, in French]
[or English]
[more info]
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.
A short version also appeared in the proceedings of
FPSAC 2012
[short version]

The vertical profile of embedded trees.
with Mireille BousquetMélou.
Electronic Journal of Combinatorics, 19(3):P46 (2012), 61 pages.
[arxiv]
[doi link]
[more info]
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.

A new combinatorial identity for unicellular maps, via a direct bijective approach.
Advances in Applied Mathematics, 47(4):874893 (2011), 20 pages.
[pdf file]
[doi link]
[related slides]
[more info]
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.
with Olivier Bernardi.
Journal of Combinatorial Theory, Series A, 118(6):17181748 (2011), 31 pages.
[pdf file]
[doi link]
[related slides, in French]
[shorter slides, in English]
[more info]
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.
A short version with less enumerative results also appeared in the proceedings of the conference
TGGT 2008
[short version]

Counting unicellular maps on nonorientable surfaces.
with Olivier Bernardi.
Advances in Applied Mathematics, 47(2):259275(2011), 17 pages.
[pdf file]
[doi link]
[related slides]
[more info]
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.
a short version also appeared in the proceedings of
FPSAC 2010
[short version]

Asymptotic enumeration and limit laws for graphs of fixed genus.
with Éric Fusy, Omer Giménez, Bojan Mohar, and Marc Noy.
Journal of Combinatorial Theory, Series A, 118(3):748777 (2011), 30 pages
[arxiv]
[doi link]
[more info]
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.

The structure of unicellular maps, and
a connection between maps of positive genus and planar labelled trees.
Probability Theory and Related Fields 147(3):415447 (2010), 33 pages.
[pdf file]
[doi link]
[more info]
(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.

A complete grammar for
decomposing a family of graphs into 3connected
components.
with
Éric Fusy, Mihyun Kang, and Bilyana
Shoilekova.
Electronic Journal of Combinatorics 15:R148(2008), 39 pages.
[pdf
file]
[doi link]
[more info]
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.

Asymptotic enumeration of
constellations and related families of maps on orientable surfaces.
Combinatorics, Probability, and Computing 18(04):477516 (2009), 40 pages
[pdf file]
[doi link]
[more info]
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.
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.
with Michel Marcus and Gilles Schaeffer.
SIAM Journal on Discrete Mathematics, 23(3):15871611 (2009), 25 pages.
[pdf file]
[doi link]
[more info]
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)

Random permutations and their discrepancy process.
DMTCS Proceedings, 2007 Conference on Analysis of Algorithms, AofA 07.
[pdf file]
[more info]
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')