ArXiv Prreprint 

Abstract: 

We define graph drawing algorithms which simultaneously generalize several classical ones. More precisely, we consider the following algorithms:

(a) Fusy's algorithm for the straight-line grid drawing of planar triangulations, based on transversal structures,

(b) Barrière and Huemmer's algorithm for the straight-line grid drawing of planar quadrangulations, based on separating decompositions,

(c) He's algorithm for the orthogonal drawing of 3-valent planar maps, based on transversal structures,

(d) Bernardi \& Fusy 's algorithm for the orthogonal drawing of 4-valent planar maps, based on 2-orientations.

We present an algorithm generalizing (a) and (b) which produces a straight line grid drawing for planar maps with faces of degree at most 4, and we present an algorithm generalizing (c) and (d) which produces an orthogonal drawing for planar maps with vertices of degree at most 4. Our two algorithms are based on a class of combinatorial structures called grand-Schnyder woods.

ArXiv Prreprint 

Abstract: 

We define some Schnyder-type combinatorial structures on a class of planar triangulations of the pentagon which are closely related to 5-connected triangulations. The combinatorial structures have three incarnations defined in terms of orientations, corner-labelings, and woods respectively. The wood incarnation consists in 5 spanning trees crossing each other in an orderly fashion. Similarly as for Schnyder woods on triangulations, it induces, for each vertex, a partition of the inner triangles into face-connected regions (5~regions here). We show that the induced barycentric vertex-placement, where each vertex is at the barycenter of the 5 outer vertices with weights given by the number of faces in each region, yields a planar straight-line drawing.

ArXiv Prreprint 

Abstract: 

We define a far-reaching generalization of Schnyder woods which encompasses many classical combinatorial structures on planar graphs. 

Schnyder woods are defined for planar triangulations as certain triples of spanning trees covering the triangulation and crossing each other in an orderly fashion. They are of theoretical and practical importance, as they are central to the proof that the order dimension of any planar graph is at most 3, and they are also underlying an elegant drawing algorithm. In this article we extend the concept of Schnyder wood well beyond its original setting: for any integer d we define a ``grand-Schnyder'' structure for (embedded) planar graphs which have faces of degree at most d and non-facial cycles of length at least d. We prove the existence of grand-Schnyder structures, provide a linear construction algorithm, describe 4 different incarnations (in terms of tuples of trees, corner labelings, weighted orientations, and marked orientations), and define a lattice for the set of grand Schnyder structures of a given planar graph. We show that the grand-Schnyder framework unifies and extends several classical constructions: Schnyder woods and Schnyder decompositions, regular edge-labelings (a.k.a. transversal structures), and Felsner woods. 

ArXiv Prreprint 

Abstract: 

The Tutte polynomial is a fundamental invariant of graphs and matroids. In this article, we define a generalization of the Tutte polynomial to oriented graphs and regular oriented matroids. To any regular oriented matroid N, we associate a polynomial invariant A_N(q,y,z), which we call the A-polynomial. The A-polynomial has the following interesting properties among many others: 

1. a specialization of A_N gives the Tutte polynomial of the unoriented matroid underlying N, 

2. when the oriented matroid N corresponds to an unoriented matroid (that is, when the elements of the ground set come in pairs with opposite orientations), the A-polynomial is equivalent to the Tutte polynomial of this unoriented matroid (up to a change of variables), 

3. the A-polynomial A_N detects, among other things, whether N is acyclic and whether N is totally cyclic. 

We explore various properties and specializations of the A-polynomial. We show that some of the known properties or the Tutte polynomial of matroids can be extended to the A-polynomial of regular oriented matroids. For instance, we show that a specialization of A_N counts all the acyclic orientations obtained by reorienting some elements of N, according to the number of reoriented elements.

ArXiv Preprint

Abstract: 

We set the foundation for a series of works aimed at proving strong relations between uniform random planar maps and Liouville quantum gravity. 

Our method relies on a bijective encoding of site-percolated planar triangulations by certain 2D lattice paths. Our bijection parallels in the discrete setting the mating-of-trees framework of Liouville quantum gravity (LQG) and Schramm-Loewner evolutions (SLE) introduced by Duplantier, Miller, and Sheffield. Combining these two correspondences allows us to relate uniform site-percolated triangulations to $\sqrt{8/3}$-LQG and Schramm-Loewner evolutions with parameter 6 (SLE$_6$). In particular, we establish the convergence of several functionals of the percolation model to continuous probabilistic structures defined in terms of $\sqrt{8/3}$-LQG and SLE$_6$. For instance, we show that the exploration tree of the percolation converges to a branching SLE$_6$, and that the collection of percolation cycles converges to the conformal loop ensemble CLE$_6$. We also prove convergence of counting measure on the pivotal points of the percolation. 

Our results play an essential role in several other works, including a program for showing convergence of the conformal structure of uniform triangulations and works which study the behavior of random walk on the uniform infinite planar triangulation.

Notes: 

Here is a  presentation  given at the Oxford Discrete Mathematics and Probability Online Seminar 

A  short abstract appears in Notices of the AMS, Volume 66 Number 4 Pages 566-567.

ArXiv Prreprint 

Abstract: 

Wouldn't it be nice to have a polynomial expression parametrizing at once the Tutte polynomial of every matroid of a given size? 

In this article, we show how to achieve this goal. The solution involves extending the definition of the Tutte polynomial from the setting of matroids to the setting of polymatroids (this is akin to the generalization from graphs to hypergraphs), and adopting a geometric point-counting perspective. 

On our way, we establish the connection between several notions: the activity-counting invariants of Kalman and Postnikov, the point-counting invariants of Cameron and Fink, and the classical corank-nullity definition of the Tutte polynomial of matroids.

ArXiv Preprint 

Abstract: 

In the 1970s, William  Tutte developed a clever algebraic approach, based on certain ``invariants'', to solve a functional equation that arises in the enumeration of properly colored triangulations.  The enumeration of plane lattice walks confined to the first quadrant is governed by similar equations, and has led in the past decade to a rich collection of attractive results dealing with the nature (algebraic, D-finite or not) of the associated generating function, depending on the set of allowed steps, taken in {-1,0,1}^2.  

We first adapt Tutte's approach to prove (or reprove) the algebraicity of all quadrant models known or conjectured to be algebraic. This includes Gessel's famous model, and the first proof ever found for one  model with weighted steps. To be applicable, the method requires the existence of two rational functions called  invariant and decoupling function respectively. When they exist, algebraicity follows almost automatically.

Then, we move to an analytic viewpoint that has already proved very powerful, leading in particular to integral expressions of the generating function in the non-D-finite cases, as well as to proofs of non-D-finiteness. We develop  in this context a weaker notion of  invariant. Now all quadrant models have invariants, and for those that have in addition a decoupling function, we obtain integral-free expressions of the generating function, and a proof that this series is differentially algebraic (that is, satisfies polynomial differential equations).

Notes: 

An extended abstract also appeared in the DMTCS proceedings of FPSAC 2016.Counting  quadrant walks via Tutte's invariant methodCounting  quadrant walks via Tutte's invariant method 

Maple Sessions:

 The main accompanying  Maple  session is this one. 

It points to four other sessions, for the calculation of  invariants, of  decoupling functions, for proving that no such function exists, and solving the algebraic models.

ArXiv Preprint

Abstract: 

Let $G$ be a graph, and let $\chi_G$ be its chromatic polynomial. For any non-negative integers $i,j$, we give an interpretation for the evaluation $\chi_G^{(i)}(-j)$ in terms of acyclic orientations. This recovers the classical interpretations due to Stanley and to Greene and Zaslavsky respectively in the cases $i=0$ and $j=0$. We also give symmetric function refinements of our interpretations, and some extensions. The proofs use heap theory in the spirit of a 1999 paper of Gessel.

ArXiv Preprint 

Abstract: 

The Tutte polynomial is a fundamental invariant of graphs. In this article, we define and study a generalization of the Tutte polynomial for directed graphs, that we name B-polynomial. The B-polynomial has three variables, but when specialized to the case of graphs (that is, digraphs where arcs come in pairs with opposite directions), one of the variables becomes redundant and the B-polynomial is equivalent to the Tutte polynomial.

We explore various properties, expansions, specializations, and generalizations of the B-polynomial, and try to answer the following questions:

1. what properties of the digraph can be detected from its B-polynomial (acyclicity, length of paths, number of strongly connected components, etc.)?

2. which of the marvelous properties of the Tutte polynomial carry over to the directed graph setting?

The B-polynomial generalizes the strict chromatic polynomial of mixed graphs introduced by Beck, Bogart and Pham. We also consider a quasisymmetric function version of the B-polynomial which simultaneously generalizes the Tutte symmetric function of Stanley and the quasisymmetric chromatic function of Shareshian and Wachs.

ArXiv Preprint

Abstract: 

We present a general bijective approach to planar hypermaps with two main results. 

First we obtain unified bijections for all classes of maps or hypermaps defined by face-degree constraints and girth constraints. To any such class we associate bijectively a class of plane trees characterized by local constraints. This unifies and greatly generalizes several bijections for maps and hypermaps. 

Second, we present yet another level of generalization of the bijective approach by considering classes of maps with non-uniform girth constraints. More precisely, we consider well-charged maps, which are maps with an assignment of charges (real numbers) on vertices and faces, with the constraints that the length of any cycle of the map is at least equal to the sum of the charges of the vertices and faces enclosed by the cycle. 

We obtain a bijection between charged hypermaps and a class of plane trees characterized by local constraints.

ArXiv Preprint

Abstract: 

We establish counting formulas and bijections for deformations of the braid arrangement. Precisely, we consider real hyperplane arrangements such that all the hyperplanes are of the form $x_i-x_j=s$ for some integer $s$. Classical examples include the braid, Catalan, Shi, semiorder and Linial arrangements, as well as graphical arrangements. We express the number of regions of any such arrangement as a signed count of decorated plane trees. The characteristic and coboundary polynomials of these arrangements also have simple expressions in terms of these trees. 

We then focus on certain ``well-behaved'' deformations of the braid arrangement that we call transitive. This includes the Catalan, Shi, semiorder and Linial arrangements, as well as many other arrangements appearing in the literature. For any transitive deformation of the braid arrangement we establish a simple bijection between regions of the arrangement and a set of plane trees defined by local conditions. This answers a question of Gessel. 

ArXiv Preprint

Abstract: 

We study the percolation model on Boltzmann triangulations using a generating function approach. More precisely, we consider a Boltzmann model on the set of finite planar triangulations, together with a percolation configuration (either site-percolation or bond-percolation) on this triangulation. 

By enumerating triangulations with boundaries according to both the boundary length and the number of vertices/edges on the boundary, we are able to identify a phase transition for the geometry of the origin cluster. 

For instance, we show that the probability that a percolation interface has length $n$ decays exponentially with $n$ except at a particular value $p_c$ of the percolation parameter $p$ for which the decay is polynomial (of order $n^{-10/3}$). Moreover, the probability that the origin cluster has size $n$  decays exponentially if $p < p_c$ and polynomially otherwise. 

The critical percolation value is $p_c=1/2$ for site percolation, and $p_c=(2\sqrt{3}-1)/11$ for bond percolation. These values coincide with critical percolation thresholds for infinite triangulations identified by Angel for site-percolation, and by Angel and Curien for bond-percolation, and we give an independent derivation of these  percolation thresholds.

Lastly, we revisit the criticality conditions for random Boltzmann maps, and argue that  at $p_c$, the percolation clusters conditioned to have size $n$ should converge toward the stable map of parameter $7/6$ introduced by Le Gall and Miermont. This enables us to derive heuristically some new critical exponents. 

Notes: 

Here are the Maple sessions for site percolation and for bond percolation.

Here is a Quanta Magazine Article  inspired by this work, and a follow up podcast.

ArXiv Preprint

Abstract: 

We present bijections for planar maps with boundaries. In particular, we obtain bijections for triangulations and quadrangulations of the sphere with boundaries of prescribed lengths. For triangulations we recover the beautiful factorized formula obtained by Krikun using a (technically involved) generating function approach. The analogous formula for quadrangulations is new. We also obtain a far-reaching generalization for other face-degrees. In fact, all the known enumerative formulas for maps with boundaries are proved bijectively in the present article (and several new formulas are obtained).<br/>

Our method is to show that maps with boundaries can be endowed with certain ``canonical'' orientations, making them amenable to the master bijection approach we developed in previous articles. As an application of our enumerative formulas, we note that they provide an exact solution of the dimer model on rooted triangulations and quadrangulations.

Notes: 

This is an update and significant extension of a previous preprint titled Bijections for maps with boundaries: Krikun's formula for triangulations, and a quadrangulation analogue.

Here is the Maple session about the  dimer model.

ArXiv Preprint

Abstract: 

We address the enumeration of $q$-coloured planar maps counted by the   number of edges and the number  of monochromatic edges. We prove that the associated generating function is differentially algebraic, that is, satisfies a  non-trivial polynomial differential equation with respect to the edge variable. We give explicitly a differential system that characterizes this series.   We then prove a similar result for planar triangulations, thus generalizing a result of Tutte  dealing with their proper $q$-colourings. In statistical physics terms, we solve the $q$-state Potts model on random planar lattices. 

This work follows a first paper by the same authors, where the generating function was proved to be algebraic for certain values of $q$, including $q=1, 2$ and $3$. It is known to be transcendental in general. In contrast, our differential system holds for an indeterminate $q$.

For certain special cases of combinatorial  interest (four colours; proper $q$-colourings; maps equipped with a spanning forest), we derive from this system, in the case of triangulations, an explicit differential equation of order $2$ defining the generating function. For general planar maps, we also obtain a differential equation of order 3 for the four-colour case and for the self-dual Potts model.

Notes: 

 Maple sessions for planar maps, and for triangulations. 

ArXiv Preprint (pdf)

Abstract: 

For a graph $G$, the generating function of rooted forests, counted by the number of connected components, can be expressed in terms of the eigenvalues of the graph Laplacian. We generalize this result from graphs to cell complexes of arbitrary dimension. This requires generalizing the notion of rooted forest to higher dimension. We also introduce orientations of higher dimensional rooted trees and forests. This leads to open questions concerning expressing homological quantities combinatorially. 

ArXiv Preprint

Abstract: 

In this article we consider several probabilistic processes defining random graphs. One of these processes appeared recently in connection with a factorization problem in the symmetric group.

For each of the probabilistic processes, we prove that the probability for the random graph to be a tree has an extremely simple expression, which is independent of most parameters of the problem. This raises many open questions.

ArXiv Preprint

Abstract: 

We prove a new formula for the generating function of multitype Cayley trees counted according to their degree distribution. Using this formula we recover and extend several enumerative results about trees. In particular, we extend some results by Knuth and by Bousquet-Melou and Chapuy about embedded trees. We also give a new proof of  the multivariate Lagrange inversion formula. 

   Our strategy for counting trees is to exploit symmetries of refined enumeration formulas: proving these symmetries is easy, and once the symmetries are proved the formulas follow effortlessly. We also adapt this strategy to recover an enumeration formula of Goulden and Jackson for cacti counted according to their degree distribution.

ArXiv Preprint

Abstract: 

We study the mixing properties of permutations obtained as a product of two uniformly random permutations of fixed cycle types. For instance, we give an exact formula for the probability that elements 1,2,...,k are in distinct cycles of the random permutation of {1,2,...,n} obtained as product of two uniformly random n-cycles.

Manuscript

Abstract: 

We study the distance-profile of the random rooted plane graph $G_n$ with $n$ edges (by a plane graph we mean a planar map with no loops nor multiple edges).  

Our main result is that the profile and radius of $G_n$ (with respect to the root-vertex),  rescaled by $(2n)^{1/4}$, converge to explicit distributions related to the Brownian snake. A crucial ingredient of our proof is a bijection we have recently introduced between rooted outer-triangular plane graphs and rooted eulerian triangulations, combined with ingredients from Chassaing and Schaeffer (2004), Bousquet-M\'elou and Schaeffer (2000), and Addario-Berry and Albenque (2013).

We also show that the result for plane graphs implies similar results for random rooted loopless maps and general maps. 

Notes: 

Manuscript

Abstract: 

This paper is concerned with the counting and random sampling of plane graphs (simple planar graphs embedded in the plane). 

Our main result is a bijection between the class of plane graphs with triangular outer face, and a class of oriented binary trees. The number of edges and vertices of the plane graph can be tracked through the bijection. Consequently, we obtain counting formulas and an efficient random sampling algorithm for rooted plane graphs (with arbitrary outer face) according to the number of edges and vertices. 

We also obtain a bijective link, via a bijection of Bona, between rooted plane graphs and $1342$-avoiding permutations.

ArXiv Preprint

Abstract: 

We study the factorizations of the permutation $(1,2,\ldots,n)$ into $k$ factors of given cycle types. Using representation theory, Jackson obtained for each $k$ an elegant formula for counting these factorizations according to the number of cycles of each factor. In the cases $k=2,3$ Schaeffer and Vassilieva gave a combinatorial proof of Jackson's formula, and Morales and Vassilieva obtained more refined formulas exhibiting a surprising symmetry property. These counting results are indicative of a rich combinatorial theory which has remained elusive to this point, and it is the goal of this article to establish a series of bijections which unveil some of the combinatorial properties of the factorizations of $(1,2,\ldots,n)$ into $k$ factors for all $k$. We thereby obtain refinements of Jackson's formulas which extend the cases $k=2,3$ treated by Morales and Vassilieva. Our bijections are described in terms of ``constellations'', which are graphs embedded in surfaces encoding the transitive factorizations of permutations.

ArXiv Preprint

Abstract: Consider a walk in the plane made of  n unit steps, with directions chosen independently and uniformly at random at each step. Rayleigh's theorem asserts that the probability for such a walk to end at a distance less than 1 from its starting point is  1/(n+1). 

We give an elementary proof of this result. We also prove the following generalization valid for any probability distribution D on the positive real numbers: if two walkers start at the same point and make respectively m and n independent steps with uniformly random directions and with lengths chosen according to  D, then the probability that the first walker ends farther away than the second is m/(m+n).

ArXiv Preprint

Abstract: 

We give two combinatorial proofs of a an elegant product formula for the number of spanning trees of the n-dimensional hypercube.

The first proof is based on the assertion that if one chooses a uniformly random rooted spanning tree of the hypercube and orient each edge from parent to child, then the parallel edges of the hypercube get orientations which are independent of one another. This independence property actually holds in a more general context and has intriguing consequences.

The second proof uses some killing involutions in oder to identify the factors in the product formula. It leads to an enumerative formula for the spanning trees of the $n$-dimensional hypercube augmented with diagonals edges, counted according to the number of edges of each type. 

We also prove more general counting formulas for the spanning trees of Cartesian products of complete graphs using a matrix-tree approach.

ArXiv Preprint

Abstract: 

This article presents unified bijective constructions for planar maps, with control on the face degrees and on the girth. Recall that the girth is the length of the smallest cycle, so that maps of girth at least $d=1,2,3$ are respectively the general, loopless, and simple maps. For each positive integer $d$, we obtain a bijection for the class of plane maps (maps with one distinguished root-face) of girth $d$ having a root-face of degree $d$. We then obtain more general bijective constructions for annular maps (maps with two distinguished root-faces) of girth at least $d$.

Our bijections associate to each map a decorated plane tree, and non-root faces of degree $k$ of the map correspond to vertices of degree $k$ of the tree. As special cases we recover several known bijections for bipartite maps, loopless triangulations, simple triangulations, simple quadrangulations, etc. Our work unifies and greatly extends these bijective constructions.

In terms of counting, we obtain for each integer~$d$ an expression for the generating function $F_d(x_d,x_{d+1},x_{d+2},\ldots)$ of plane maps of girth~$d$ with root-face of degree $d$, where the variable~$x_k$ counts the non-root faces of degree~$k$. The expression for~$F_1$ was already obtained bijectively by Bouttier, Di~Francesco and Guitter, but for $d\geq 2$ the expression of~$F_d$ is new. We also obtain an expression for the generating function $\G_{p,q}^{(d,e)}(x_d,x_{d+1},\ldots)$ of annular maps with root-faces of degrees $p$ and $q$, such that cycles separating the two root-faces have length at least $e$ while other cycles have length at least~$d$.

Our strategy is to obtain all the bijections as specializations of a single ``master bijection'' introduced by the authors in a previous article. In order to use this approach, we exhibit certain ``canonical orientations'' characterizing maps with prescribed girth constraints.

ArXiv Preprint

Abstract: 

A unicellular map is the embedding of a connected graph in a surface in such a way that the complement of the graph is simply connected. In a famous article, Harer and Zagier established a formula for the generating function of unicellular maps counted according to the number of vertices and edges. The keystone of their approach is a counting formula for unicellular maps on orientable surfaces with n edges, and with vertices colored using every color in [q] (adjacent vertices are authorized to have the same color). 

We give an analogue of this formula for general (locally orientable) surfaces.

Our approach is bijective and is inspired by Lass's proof of the Harer-Zagier formula. We first revisit Lass's proof and twist it into a bijection between unicellular maps on orientable surfaces with vertices colored using every color in [q], and maps with vertex set [q] on orientable surfaces with a marked spanning tree. The bijection immediately implies Harer-Zagier's formula and a formula by Jackson concerning bipartite unicellular maps. It also shed a new light on constructions by Goulden and Nica, Schaeffer and Vassilieva, and Morales and Vassilieva. We then extend the bijection to general surfaces and obtain a correspondence between unicellular maps on general surfaces with vertices colored using every color in [q],  and maps on orientable surfaces with vertex set [q] with a marked planar submap. This correspondence gives an analogue of the Harer-Zagier formula for general surfaces. 

We also show that this formula implies a recursion formula due to Ledoux for the numbers of unicellular maps with given numbers of vertices and edges.

ArXiv Preprint

Abstract: 

A d-angulation is a planar map with faces of degree d. We present for each integer d\geq 3 a bijection between the class of d-angulations of girth d (i.e., with no cycle of length less than d) and a class of decorated plane trees. Each of the bijections is obtained by specializing a ``master bijection'' which extends an earlier construction of the first author. 

Our construction unifies known bijections by Fusy, Poulalhon and Schaeffer for triangulations (d=3) and by Schaeffer for quadrangulations (d=4). For d\geq 5, both the bijections and the enumerative results are new. 

We also extend our bijections so as to enumerate p-gonal d-angulations (d-angulations with a simple boundary of length p) of girth d. We thereby recover bijectively the results of Brown for simple p-gonal triangulations and simple 2p-gonal quadrangulations and establish new results for d\geq 5. 

A key ingredient in our proofs is a class of orientations characterizing d-angulations of girth d. Earlier results by Schnyder and by De Fraysseix and Ossona de Mendez showed that simple triangulations  and simple quadrangulations  are characterized by the existence of orientations having respectively indegree 3 and 2 at each inner vertex. 

We extend this characterization by showing that a d-angulation has girth d if and only if the graph obtained by duplicating each edge d-2 times admits an orientation having indegree d at each inner vertex. 

Notes: 

A related extended abstract (with less results) appeared in the DMTCS proceedings of FPSAC 2010.

ArXiv Preprint

Abstract: 

Schnyder woods are decompositions of simple triangulations into three edge-disjoint spanning trees  crossing each other in a specific way. In this article, we define a generalization of Schnyder woods to d-angulations (plane graphs with faces of degree d) for all  d\geq 3. A \emph{Schnyder decomposition} is a set of <em>d</em> spanning forests crossing each other in a specific way, and such that each internal edge is part of exactly d-2 of the spanning forests. 

We show that a Schnyder decomposition exists if and only if the girth of the <em>d</em>-angulation is d. As in the case of Schnyder woods (d=3), there are alternative  formulations in terms of orientations (``fractional'' orientations when <em>d\geq 5</em>) and in terms of corner-labellings.   Moreover, the set of Schnyder decompositions on a fixed <em>d</em>-angulation of girth <em>d</em> is  a distributive lattice.

We also show that  the structures dual to Schnyder decompositions (on <em>d</em>-regular plane graphs of mincut <em>d</em> rooted at a vertex <em>v^*</em>) are decompositions  into <em>d</em> spanning trees rooted at <em>v^*</em> such that each edge not incident to <em>v^*</em> is used  in opposite directions by two trees.  Additionally, for even values of <em>d</em>, we show that a subclass of Schnyder decompositions, which are called even, enjoy additional properties that yield  a reduced formulation; in the case <em>d=4</em>, these correspond to well-studied structures on simple quadrangulations (2-orientations and partitions into 2 spanning trees).

In the case d=4, the dual of even Schnyder decompositions yields (planar) orthogonal and straight-line drawing algorithms.  For a 4-regular plane graph G of mincut 4 with n vertices plus a  root-vertex,  the non-root vertices of G are placed on a (n-1) x (n-1) grid  according to a permutation pattern, and in the orthogonal drawing each of the  edges has exactly one bend.  

ArXiv Preprint

Abstract: 

It is well-known that the triangulations of the disc with n+2 vertices on its boundary are counted by the Catalan number C(n)=1/(n+1) Binomial(2n,n). This paper deals with the generalization of this problem to any arbitrary compact surface S with boundaries. 

We obtain the asymptotic number of simplicial decompositions of the surface S with n vertices on its boundary. More generally, we determine the asymptotic number of dissections of S when the faces are d-gons with d belonging to a set D of admissible degrees contained in {3,4,5,...}. We also give the limit laws of certain parameters of such dissections.

Manuscript (pdf)

Abstract: 

We present a new algorithm for the random generation of regular languages. For generating a uniformly random word of length n in a given regular language, our algorithm has worst-case space bit-complexity O(n) and mean time bit-complexity O(n). 

The previously best algorithm, due to  Denise and Zimmermann [Theoret. Comput. Sci. 1999], has  worst-case space bit-complexity O(n^2) and  mean time bit-complexity O(n log(n)).  The Denise et al. algorithm was obtained by performing a floating-point optimization on the general recursive method  formalized by Nijenhuis and Wilf (and further developed by Flajolet, Zimmermann and Van Cutsem). Our algorithm combines the floating-point optimization with a new divide-and-conquer scheme.

ArXiv Preprint

Abstract: 

We address the enumeration of properly <em>q</em>-colored planar maps, or more precisely, the enumeration of planar maps <em>M</em> weighted by their chromatic polynomial \chi_M(q) and counted by the number of vertices and faces. We prove that the associated generating function is algebraic when q is of the form 2+2 cos(j\pi/m), for integers 0<j<m.  This includes the two integer values q=2 and q=3.  

We extend this to planar maps weighted by their Potts polynomial P_M(q,\nu), which counts all q-colorings  (proper or not) by the number of monochromatic edges. We then  prove similar results for planar triangulations, thus generalizing some results of Tutte which dealt with their proper q-colorings. In statistical physics terms, the problem we study consists in solving the Potts model on random planar lattices. 

From  a technical viewpoint, our approach involves solving non-linear equations with two catalytic variables. To our knowledge, this is the first time such equations are being solved since Tutte's remarkable solution of  properly q-colored triangulations. 

Notes: 

ArXiv Preprint

Abstract: 

We consider maps on orientable surfaces. A map is called unicellular if it has a single face. A covered map is a map (of genus g) with a marked unicellular spanning submap (which can  have any genus in {0,1,...,g}).  Our main result is a bijection between covered maps with $n$ edges and genus $g$ and pairs made of a plane tree with $n$ edges and a unicellular bipartite map of genus $g$ with $n+1$ edges. In the planar case, covered maps are maps with a marked spanning tree  and our bijection specializes into a construction previously obtained by the first author.

Covered maps can also be seen as shuffles of two unicellular maps (one representing the unicellular submap, the other representing the dual unicellular submap). Thus, our bijection gives a correspondence between shuffles of unicellular maps, and pairs made of a plane tree and a unicellular bipartite map. In terms of counting, this establishes the equivalence between a formula due to Harer and Zagier for general unicellular maps, and a formula due to Jackson for bipartite unicellular maps.

We also show that the bijection of Bouttier, Di Francesco and Guitter (which  generalizes a previous bijection by Schaeffer) between bipartite maps and so-called well-labelled mobiles can be obtained as a special case of our bijection.

ArXiv Preprint

Abstract: 

A unicellular map is the embedding of a connected graph in a surface in such a way that the complement of the graph is a topological disk. 

In this paper we present a bijective link between unicellular maps on a non-orientable surface and unicellular maps of a lower topological type, with distinguished vertices. From that we obtain a recurrence equation that leads to (new) explicit counting formulas for non-orientable unicellular maps of fixed topology. In particular, we give exact formulas for the precubic case (all vertices of degree 1 or 3), and asymptotic formulas for the general case, when the number of edges goes to infinity. 

Our strategy is inspired by recent results obtained by the second author for the orientable case, but significant novelties are introduced: in particular we construct an involution which, in some sense, "averages" the effects of non-orientability.

Notes: 

An extended abstract also appeared in the DMTCS proceedings of FPSAC 2010.

Preprint (pdf)

Abstract: 

A minor-closed  class of graphs is a set of labelled graphs which is closed under isomorphism and under taking minors. For a minor-closed class G, let g_n be the number of graphs in G which have n vertices.  The growth constant of G is

\gamma = \limsup (g_n/n!)^{1/n}. 

We study the properties of the set \Gamma of growth constants of minor-closed classes of graphs. Among other results, we show that \Gamma does not contain any number in the interval [0,2], besides 0,1,\xi and 2, where \xi \approx 1.76. 

An infinity of further gaps isfound by determining all the possible growth constants between 2 and \delta \approx 2.25159. Our results give in fact a complete characterization of all the minor-closed classes with growth constant at most \delta in terms of their excluded minors.

Notes: 

An earlier unpublished manuscript  contains less results on factorial classes, but more on sub-factorial classes. 

ArXiv Preprint

Abstract: 

A well-labelled positive path of size n is a pair (p,\sigma) made of a word p=p_1p_2...p_{n-1} on the alphabet {-1, 0,+1} such that the sum of the letters of any prefix is non-negative, together with a permutation \sigma of {1,2,...,n} such that p_i=-1 implies \sigma(i)<\sigma(i+1), while p_i=1 implies \sigma(i)>\sigma(i+1). We establish a bijection between well-labelled positive paths of size n and matchings (i.e. fixed-point free involutions) on {1,2,...,2n}. This proves that the number of well-labelled positive paths is (2n-1)!!. By specialising our bijection, we also prove that the number of permutations of size n such that each prefix has no more ascents than descents is [(n-1)!!]^2 if n is even and n!!(n-2)!! otherwise. Our results also prove combinatorially that the n-dimensional polytope consisting of all points (x_1,...,x_n) in [-1,1]^n such that the sum of the first j coordinates is non-negative for all j=1,2,...,n has volume (2n-1)!!/n!.

ArXiv Preprint 

Abstract: 

The Stanley lattice, Tamari lattice and Kreweras lattice are three partial orders defined on the set of Catalan objects of a given size. These lattices are ordered by inclusion: the Stanley lattice is an extension of the Tamari lattice which is an extension of the Kreweras lattice. The Stanley order can be defined on the set of Dyck paths of size n as the relation of being above. Hence, intervals in the Stanley lattice are pairs of non-crossing Dyck paths. 

In a former article, the second author defined a bijection F between pairs of non-crossing Dyck paths and the realizers of triangulations (or Schnyder woods). We give a simpler description of the bijection F. Then, we study the restriction of F to Tamari's and Kreweras' intervals. We prove that F induces a bijection between Tamari intervals and minimal realizers. This gives a bijection between Tamari intervals and triangulations. We also prove that  F induces a bijection between Kreweras intervals and the (unique) realizers of stack triangulations. Thus, F induces a bijection between Kreweras intervals and stack triangulations which are known to be in bijection with ternary trees.

Notes: 

An extended abstract also appeared in DMTCS proceedings of FPSAC 2007.

ArXiv Preprint 

Abstract: 

Mayer's theory of cluster integrals allows one to write the partition function of a gas model as a generating function of weighted graphs. Recently, Labelle, Leroux and Ducharme have studied the graph weights arising from the one-dimensional hard-core gas model and noticed that the sum of the weights over all connected graphs with n vertices is (-n)^(n-1). This is, up to sign, the number of rooted Cayley trees on n vertices and the authors asked for a combinatorial explanation. The main goal of this article is to provide such an explanation.

ArXiv Preprint 

Abstract: 

We define a bijection between spanning subgraphs and orientations of graphs and explore its enumerative consequences regarding the Tutte polynomial. We obtain unifying bijective proofs for all the evaluations T(G;i,j),i,j in {0,1,1}  of the Tutte polynomial in terms of subgraphs, orientations, outdegree sequences and sandpile configurations.  For instance, for any graph G, we obtain a bijection between connected subgraphs (counted by T(G;1,2)) and root-connected orientations, a bijection between forests (counted by T_G(2,1)) and outdegree sequences and bijections between spanning trees (counted by T(G;1,1)), root-connected outdegree sequences and recurrent sandpile configurations.<br/>

All our proofs are based on a single bijection F between the spanning subgraphs and the orientations that we specialize in various ways. The bijection F is closely related to a recent characterization of the Tutte polynomial relying on combinatorial embeddings of graphs, that is, on a choice of cyclic order of the edges around each vertex. 

ArXiv Preprint 

Abstract: 

We solve three enumerative problems concerning families of planar maps. More precisely, we establish algebraic equations for the generating function of loopless triangulations in which  all vertices have  degree at least d, for a certain value d chosen in {3, 4, 5}. The originality of the problem lies in the fact that degree restrictions are placed both on vertices and faces. 

Our proofs first follow Tutte's classical approach: we decompose maps by deleting the root-edge and translate the decomposition into an equation satisfied by the generating function of the maps under consideration. Then, we proceed to solve the equations obtained using a recent technique that extends the so-called quadratic method.

Notes: 

A related extended abstract also appeared in the proceedings of FPSAC 2005.

ArXiv Preprint 

Abstract: 

We give a new characterization of the Tutte polynomial of graphs. Our characterization is formally close (but inequivalent) to the original definition given by Tutte as the generating function of spanning trees counted according to activities. Tutte's notion of activity requires a choice of a linear order on the edge set (though the generating function of the activities is, in fact, independent of this order). We define a new notion of activity, the embedding-activity, which requires a choice of a combinatorial embedding of the graph, that is, a cyclic order of the edges around each vertex. We prove that the Tutte polynomial  equals the generating function of spanning trees counted according to  embedding-activities. This generating function is, in fact, independent of the embedding.

ArXiv Preprint 

Abstract: 

We consider lattice walks in the plane starting at the origin, remaining in the first quadrant i,j>= 0 and made of West, South and North-East steps. In 1965, Germain Kreweras discovered a remarkably simple formula giving the number of these walks (with prescribed length and endpoint). Kreweras' proof was very involved and several alternative derivations have been proposed since then. But the elegant simplicity of the counting formula remained unexplained. We give the first purely combinatorial explanation of this formula. Our approach is based on a bijection between Kreweras walks and triangulations with a distinguished spanning tree. We obtain simultaneously a bijective way of counting loopless triangulations.

Notes: 

An related extended abstract also appeared in the proceedings of FPSAC 2006.

ArXiv Preprint 

Abstract: 

The number of  tree-rooted maps, that is, rooted planar maps with a distinguished spanning tree, of size n is C(n)C(n+1) where C(n)=Binomial(2n,n)/(n+1) is the nth Catalan number.  We present a (long awaited) simple bijection which explains this result. Then, we prove that our bijection is isomorphic to a former recursive construction on shuffles of parenthesis systems due to Cori, Dulucq and Viennot.

Manuscript (pdf)

Notes: Completed at LaBRI, Universite de Bordeaux, 2006.

Manuscript (pdf)

Notes: Completed at Ecole Normale Superieure de Paris, 2003.

Manuscript (pdf)

Notes: Completed at Courant Institute,  New York University, 2002.

Manuscript (pdf)

Notes: Completed at INRIA Sophia-Antipolis, 2001.