Preprints

• Short Synchronizing Words for Random Automata
  with Guillem Perarnau
  Conference version accepted to SODA 2023.
  [arxiv] [more info] We prove that a uniformly random automaton with n states on a 2-letter alphabet has a synchronizing word of length O(n1/2logn) with high probability (w.h.p.). That is to say, w.h.p. there exists a word ω of such length, and a state v0, such that ω sends all states to v0. Prior to this work, the best upper bound was the quasilinear bound O(nlog3n) due to Nicaud (2016). The correct scaling exponent had been subject to various estimates by other authors between 0.5 and 0.56 based on numerical simulations, and our result confirms that the smallest one indeed gives a valid upper bound (with a log factor). Our proof introduces the concept of w-trees, for a word w, that is, automata in which the w-transitions induce a (loop-rooted) tree. We prove a strong structure result that says that, w.h.p., a random automaton on n states is a w-tree for some word w of length at most (1+ϵ)log2(n), for any ϵ>0. The existence of the (random) word w is proved by the probabilistic method. This structure result is key to proving that a short synchronizing word exists.
  Check also these slides.
• Topological recursion for Orlov-Scherbin tau functions, and constellations with internal faces
  with Valentin Bonzom, Séverin Charbonnier, Elba Garcia-Failde.
  [arxiv] [more info] We study the correlators Wg,n arising from Orlov-Sherbin 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 W0,1, and the "cylinder" function W0,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.
  
• Random partitions under the Plancherel-Hurwitz measure, high genus Hurwitz numbers and maps
  with Baptiste Louf and Harriet Walsh.
  [arxiv] [more info] We study the asymptotic behaviour of random integer partitions under a new probability law that we introduce, the Plancherel-Hurwitz measure. This distribution, which has a natural definition in terms of Young tableaux, is a deformation of the classical Plancherel measure which appears naturally in the context of Hurwitz numbers, enumerating certain transposition factorisations in symmetric groups. We study a regime in which the number of factors in the underlying factorisations grows linearly with the order of the group, and the corresponding topological objects, Hurwitz maps, are of high genus. We prove that the limiting behaviour exhibits a new, twofold, phenomenon: the first part becomes very large, while the rest of the partition has the standard Vershik-Kerov-Logan-Shepp limit shape. As a consequence, we obtain asymptotic estimates for unconnected Hurwitz numbers with linear Euler characteristic, which we use to study random Hurwitz maps in this regime. This result can also be interpreted as the return probability of the transposition random walk on the symmetric group after linearly many steps.
  Check also my recorded talk (in French) at the Journées du GDR-IM in Lille.
• Note on the density of ISE and a related diffusion
  with Jean-François Marckert.
  [arxiv] [more info] The integrated super-Brownian excursion (ISE) is the occupation measure of the spatial component of the head of the Brownian snake with lifetime process the normalized Brownian excursion. It is a random probability measure on $\mathbb{R}$, and it is known to describe the continuum limit of the distribution of labels in various models of random discrete labelled trees. We show that $f_{ISE}$, its (random) density has a.s. a derivative $f'_{ISE}$ which is continuous and $\left(\frac{1}{2}-a\right)$-Hölder for any $a >0$ but for no $a<0$ (proving a conjecture of Bousquet-Mélou and Janson). We conjecture that $f_{ISE}$ can be represented as a second-order diffusion of the form $$df'_{ISE}(t) = \sqrt{2f_{ISE}(t)}\, dB_t + g\left(f'_{ISE}(t), f_{ISE}(t),\int_{-\infty}^t f_{ISE}(s)ds\right)dt,$$ for some continuous function $g$, for $t>0$, and we give a number of remarks and questions in that direction. The proof of regularity is based on a moment estimate coming from a discrete model of trees, while the heuristic of the diffusion comes from an analogous statement in the discrete setting, which is a reformulation of explicit product formulas of Bousquet-Mélou and the first author (2012).
• Enumeration of non-oriented maps via integrability
  with Valentin Bonzom and Maciej Dołęga.
  To appear in Algebraic Combinatorics, special issue in honor of Ian Goulden and David Jackson.
  [arxiv] [more info] In this note, we examine how the BKP structure of the generating series of several models of maps on non-oriented surfaces can be used to obtain explicit and/or efficient recurrence formulas for their enumeration according to the genus and size parameters. Using techniques already known in the orientable case (elimination of variables via Virasoro constraints or Tutte equations), we naturally obtain recurrence formulas with non-polynomial coefficients. This non-polynomiality reflects the presence of shifts of the charge parameter in the BKP equation. Nevertheless, we show that it is possible to obtain non-shifted versions, meaning pure ODEs for the associated generating functions, from which recurrence relations with polynomial coefficients can be extracted. We treat the cases of triangulations, general maps, and bipartite maps. These recurrences with polynomial coefficients are conceptually interesting but bigger to write than those with non-polynomial coefficients. However they are relatively nice-looking in the case of one-face maps. In particular we show that Ledoux's recurrence for non-oriented one-face maps can be recovered in this way, and we obtain the analogous statement for the (bivariate) bipartite case.
  

Papers (published or in press)

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.
If you prefer to view my papers on arxiv, click here.

• Non-orientable branched coverings, b-Hurwitz 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 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.
  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 Jucys-Murphy 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 (case-free) formulas for the weighted enumeration of factorizations of Coxeter elements into products of reflections valid in any well-generated reflection group W, in terms of the spectrum of an associated operator, the W-Laplacian. 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 Jucys-Murphy 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 W-Laplacian 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.
• b-monotone 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 non-oriented surfaces. We give an evolution (cut-and-join) 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 non-oriented 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\'ezin-Gross-Witten integral, which we solve explicitly in terms of Pfaffians in the case of even multiplicities.
  
• Counting chains in the noncrossing partition lattice via the W-Laplacian
  with Theo Douvropoulos.
  Journal of Algebra 602 (2022) 381-404.
  [arxiv] [doi link] [more info] 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.
  
• On the number of coloured triangulations of d-manifolds
  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 d-dimensional 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 3-manifolds with n tetrahedra. Our results also imply that random coloured triangulations of 3-manifolds have a sublinear number of vertices. Our upper bounds apply in particular to coloured d-spheres 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 edge-coloured graphs having the property that each 3-coloured 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 tau-functions 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 Christoffel-Darboux 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 Addario-Berry, Omer Angel,Éric Fusy, Christina Goldschmidt.
  Proceedings of the 2018 Annual ACM-SIAM 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 i-th agent from the next one in clockwise order around the graph.
  Check the slides! (including a one-slide proof of the main result!).
  The probability that a journal version of this paper appears decreases with time.
• Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh 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 bridge-addable 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 bridge-addable 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 bridge-alterable classes, independently proved by Addario-Berry, 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 tg-recurrence
  Probab. Theory Related Fields 174 (2019), no. 1-2, 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(g-1)/2}12^n\) when \(g\) is fixed and \(n\) tends to infinity. The constants \(t_g\) can be computed thanks to the non-linear "\(t_g\)-recurrence", strongly related to the KP hierarchy and the double scaling limit of the one-matrix 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,1-X_g\) are the masses of the nearest-neighbour 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\) nearest-neighbour 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 bridge-addable 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 bridge-addable 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 bridge-addable and Gn is a uniform n-vertex 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 bridge-addable class and the random graph Gn is connected with probability close to epx(−1/2), then Gn is asymptotically close to a uniform n-vertex random forest in some local sense. For example, if the probability converges to epx(−1/2), then Gn converges in the sense of Benjamini-Schramm to the uniform infinite random forest. This result is reminiscent of so-called "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, 777-826 (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 Christoffel-Darboux 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 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 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. 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), 479-539.
  [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 so-called boson-fermion 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 transfer-matrix 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 edge-probability 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, 381-418 (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 Littlewood-type 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/Guay-Paquet/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 even-faced maps (unconventionally called "bipartite maps" in his work). However, the present paper requires no previous knowledge of this topic and comes with elementary (complex-analysis-free) 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..d-Avoiding 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 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.
• 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 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.
  A shorter version (with only the two-parameter 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): 919-939 (2014).
  [arxiv] [doi link] [related slides] [more info] 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.
• The local limit of unicellular maps in high genus
  with Omer Angel, Nicolas Curien, and Gourab Ray.
  Electron. Commun. Probab. 18 (2013), 1-8.
  [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 Galton-Watson 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 2-connected and 3-connected embedded (maps) and unembedded planar graphs.
  A short version was presented in the conference AofA 2010.
• The representation of the symmetric group on m-Tamari intervals.
  with Mireille Bousquet-Mélou and Louis-François Préville-Ratelle.
  Advances in Mathematics, 247:309-342 (2013).
  [arxiv] [doi link] [more info] An m-ballot path of size n is a path on the square grid consisting of north and east unit steps, starting at (0,0), ending at (mn,n), and never going below the line {x=my}. The set of these paths can be equipped with a lattice structure, called the m-Tamari lattice and denoted by T_n^{m}, which generalizes the usual Tamari lattice T_n obtained when m=1. This lattice was introduced by F. Bergeron in connection with the study of diagonal coinvariant spaces in three sets of n variables. The representation of the symmetric group S_n on these spaces is conjectured to be closely related to the natural representation of S_n on (labelled) intervals of the m-Tamari lattice, which we study in this paper. An interval [P,Q] of T_n^{m} is labelled if the north steps of Q are labelled from 1 to n in such a way the labels increase along any sequence of consecutive north steps. The symmetric group S_n acts on labelled intervals of T_n^{m} by permutation of the labels. We prove an explicit formula, conjectured by F. Bergeron and the third author, for the character of the associated representation of S_n. In particular, the dimension of the representation, that is, the number of labelled m-Tamari intervals of size n, is found to be \(\) (m+1)^n(mn+1)^{n-2}. \(\) These results are new, even when m=1. The form of these numbers suggests a connection with parking functions, but our proof is not bijective. The starting point is a recursive description of m-Tamari intervals. It yields an equation for an associated generating function, which is a refined version of the Frobenius series of the representation. The form of this equation is highly non-standard: it involves two additional variables x and y, a derivative with respect to y and iterated divided differences with respect to x. The hardest part of the proof consists in solving it, and we develop original techniques to do so.
  NOTE: some techniques used in this paper are common with our (unsubmitted) manuscript ''Tamari lattices and parking functions: proof of a conjecture of F. Bergeron'' below, which dealt only with the enumerative case. It may be a good introduction to our techniques.
  A 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: [previous-manuscript-arxiv]. 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. 28-1 (2014), pp. 226-239.
  [arxiv] [doi link] [more info] Tuza conjectured that for every graph G, the maximum size {\nu} of a set of edge-disjoint triangles and minimum size {\tau} of a set of edges meeting all triangles, satisfy {\tau} at most 2{\nu}. We consider an edge-weighted version of this conjecture, which amounts to packing and covering triangles in multigraphs. Several known results about the original problem are shown to be true in this context, and some are improved. In particular, we answer a question of Krivelevich who proved that {\tau} is at most 2{\nu}* (where {\nu}* is the fractional version of {\nu}), and asked if this is tight. We prove that {\tau} is at most 2{\nu}*-sqrt({\nu}*)/4 and show that this bound is essentially best possible.
• A 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 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.
  A short version also appeared in the proceedings of FPSAC 2012 [short version]
• The vertical profile of embedded trees.
  with Mireille Bousquet-Mé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 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.
• A new combinatorial identity for unicellular maps, via a direct bijective approach.
  Advances in Applied Mathematics, 47(4):874-893 (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 degree-restricted.
  A short version also appeared in the proceedings of FPSAC 2009. ("best student paper award") [short version]
• A bijection for covered maps, or a shortcut between Harer-Zagier's and Jackson's formulas.
  with Olivier Bernardi.
  Journal of Combinatorial Theory, Series A, 118(6):1718-1748 (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. 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.
  A short version with less enumerative results also appeared in the proceedings of the conference TGGT 2008 [short version]
• Counting unicellular maps on non-orientable surfaces.
  with Olivier Bernardi.
  Advances in Applied Mathematics, 47(2):259-275(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 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 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):748-777 (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(g-1)/2-1}\gamma^n n! \), where \(c^{(g)} >0\), and \(\gamma \approx 27.23\) is the exponential growth rate of planar graphs. This generalizes the result for the planar case \(g=0\), obtained by Giménez and Noy.
  An analogous result for non-orientable surfaces is obtained. In addition, it is proved that several parameters of interest behave asymptotically as in the planar case. It follows, in particular, that a random graph embeddable in \(\mathbb{S}_g\) has a unique 2-connected component of linear size with high probability.
• The structure of unicellular maps, and a connection between maps of positive genus and planar labelled trees.
  Probability Theory and Related Fields 147(3):415-447 (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 fixed-genus large-size limits).
  A unicellular map is a map which has only one face. We give a bijection between a dominant subset of rooted unicellular maps of fixed genus and a set of rooted plane trees with distinguished vertices, which leads to an easy asymptotic counting of unicellular maps of fixed genus. From the labelled case, we obtain new connections between maps of positive genus and the ISE random measure. For example, we obtain a description of the limiting profile of bipartite quadrangulations of genus g in terms of the ISE.
• A complete grammar for decomposing a family of graphs into 3-connected components.
  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 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.
  Combinatorics, Probability, and Computing 18(04):477-516 (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: 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 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):1587-1611 (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(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)
• 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 "process-valued" 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')

Teaching and lecture notes

➪ En septembre et octobre 2022, j'interviens pour cinq séances dans le cours « Aspects algorithmiques de la combinatoire » dans le M2 MPRI. Toutes les informations sont disponibles ici.

I sometimes teach. Here is some material:

• Combinatoire I et Combinatoire II, 2x24 de cours (donné en 2018/2019 puis 2019/2020) dans le M2 de Maths Fondamentales.
  Page dédiée.
  
• Maps and Algebraic Combinatorics (in French).
  ➪ Minicourse given in 2017 at the Journées Aléa in CIRM. The slides (follow link above) serve as lecture notes, see also the exercises, everything is in French.
• Combinatorics lecture notes (in English) (a draft that will not evolve anymore)
  ➪ Notes written between 2011 and 2017 when I was teaching (about 12-20 hours a year, not every year) in the Combinatorics course of the M2 program MPRI.
• Introduction to map enumeration (in English).
  ➪ Lecture notes and exercise sheet and slides of the first lecture for a course given in summer 2014, at the Algorithmic and Enumerative Combinatorics (AEC) Summer School in Hagenberg, Austria.

Other info

• Places where I have worked:
  • Since 2010: CNRS research scientist at IRIF (``Directeur de Recherche'' since 2019). With a 2-year visit to Montréal, Canada:
    • 2015/2016: CRM (member of the CNRS UMI program)
    • 2014/2015: Discrete Math group in McGill.
  • 2009/2010: PIMS postdoc in the Discrete Math Group at Simon Fraser University, Vancouver (Burnaby) Canada. Supervisor: Bojan Mohar.
  • 2007/2009: PhD student in École Polytechnique (LIX). Thesis defended June 9, 2009. Supervisor: Gilles Schaeffer.
  • I studied four years in ENS including one year in Orsay and interrupted by one year in CMDL.
• Postdocs supervised
  • Maciej Dolęga, 2013-2015.
  • Dan Betea (co-advised with Sylvie Corteel), 2016-2017.
  • Theodosios Douvropoulos, 2017-2020.
  • Cyril Marzouk, 2018-2019.
  • Luca Lionni, 2019.
  • Elba Garcia-Failde, 2020-2021.
  • Séverin Charbonnier, since September 2021.
• Students supervised
  • Julien Courtiel (Master's thesis), 2011.
  • Wenjie Fang (PhD co-advised with Mireille Bousquet-Mélou), 2012-2016. Now associate professor in Marne-La-Vallée. Congratulations to Wenjie for this!
  • Baptiste Louf (PhD student, 2017-2020). Now a postdoc in Uppsala. Congratulations to Baptiste for this!
  • Harriet Walsh (PhD co-advised with Jérémie Bouttier), since 2019.
  • Houcine Ben Dali (PhD co-advised with Valentin Feray), since 2021.
• Projects or grants:
  • 2017/2022: ERC Starting Grant, projet CombiTop. See here or here or here for more information.
  • 2017: I coorganised the program Combinatorics and Interactions (combi17) at IHP.
  • 2013/2017: Project Émergences, Combinatoire à Paris, funded by the city of Paris (project coordinator)
  • 2012/2016: Project Cartaplus, funded by the ANR (project coordinator).
• Editorial work:
  • Member of the editorial board of the Canadian Journal of Mathematics and Canadian Mathematical Bulletin (2017-2021 and 2023-2027).
  • Member of the program committee of FPSAC 2018 and FPSAC 2022.
• Theses – for French readers
  • PhD thesis, June 2009, Combinatoire bijective des cartes de genre supérieur (prix de thèse de l'École Polytechnique 2010).
  • Habilitation thesis, April 2018, Rencontres autour de la combinatoire des cartes.

• Archives (local copies of old websites kept here for reference, not updated anymore)
  • combi17 (thematic program at IHP).
  • Combinatoire à Paris (collaborative ``Émergence'' grant from the city of Paris).
  • Cartaplus (collaborative grant from the ANR).
  • FPSAC'13 (a wonderful combinatorics conference, in Paris!).