It is well known that the generating function of planar maps is algebraic. In this talk, we discuss similar properties for colored maps. Given $q$ colors, we consider the number $a_n(q)$ of properly colored planar maps with $n$ edges. The number $a_n(q)$ is a polynomial function of $q$ since it is the sum of the chromatic polynomials of all maps of size $n$. We prove that the generating function $F(q,z)=\sum a_n(q) z^n$ of colored maps is algebraic, whenever the number of colors is of the form $q=2+2 cos(k pi /m)$. Similar results hold more generally for the generating function of maps weighted by their Tutte polynomial (equivalently, the partition function of the Potts model on maps).
This is a joint work with Mireille Bousquet-Melou.
We consider the generating function for rooted planar maps counted according to the face degree distribution. It can be determined via the Tutte equation, introducting a `catalytic' variable associated to the root face degree. Alternatively, it can be obtained using a bijection with suitable trees. We show a connection between these two approaches, involving the continued fraction expansion with respect to the catalytic variable. The coefficients appearing in this expansion can be interpreted as generating functions for maps with two points at prescribed distance. We derive a formula for these coefficients using classical results on continued fractions, proving and generalizing a conjecture found in 2003 with P. Di Francesco. If time allows, we shall also comment on the relation with matrix models and orthogonal polynomials.
This is joint work with Emmanuel Guitter.
It is known that the number of rooted maps of fixed genus g with n edges behaves as t_g n^{5(g-1)/2} 12^n, when n tends to infinity. Moreover, both the constant t_g and the exponent 5(g-1)/2 are "universal", ie they appear in similar asymptotic formulas for several classes of maps on surfaces (for example, degree-restricted). In this talk, I will present two bijections that "explain" these facts in concrete terms. The first one relates maps of genus g to certain labelled one-face maps of genus g called g-mobiles. The second one relates one-face maps of any genus to trees with distinguished vertices. At the end, one is left with labelled trees with distinguished vertices on which the exponents are easy to understand. As a byproduct, we provide a new expression of t_g in terms of random labelled trees.
We come back to a bijection between rooted maps embedded on an orientable surface and indecomposable matchings. In this bijection the number of vertices of the map corresponds to the left-to-right maxima of the matchings. Some open questions and conjectures on the number of indecomposable matchings will be presented.
A series parallel graph is obtained by series and parallel edge extensions of a forest (or equivalently it is a graph without K_4 as a minor). It is proved that that the maximum degree $\Delta_n$ of a random vertex labelled series-parallel graphs with $n$ vertices satisfies $\Delta_n/\log n \to c$ in probability and $\mathbb{E}\, \Delta_n \sim c \log n$ for a computable constant $c\approx 3.4827$. The proof uses a special singularity analysis of multivariate generating function of rooted and double rooted series parallel graphs and an application of the first and second moment method.
This is joint work with O. Gimenez and M.Noy (UPC Barcelona).
Liouville quantum gravity in two dimensions is described by the "random Riemannian manifold" obtained by changing the Lebesgue measure $dz$ in the plane by a random conformal factor $\exp [\gamma h(z)]$, where $h(z)$ is a random function called the Gaussian Free Field, and $\gamma$ a parameter. This "random surface" is believed to be the continuum scaling limit of certain discretized random surfaces that can be studied with combinatorics and random matrix theory. A famous formula, due to Knizhnik, Polyakov and Zamolodchikov in '88, relates standard critical exponents in the Euclidean plane to their counterparts on the random surfaces mentioned above. We describe a recent proof of the KPZ formula in the probabilistic setting given above.
This is joint work with Scott Sheffield, MIT.
Hurwitz numbers count the number of ramified coverings of the Riemann sphere, with a given genus and branching structure. In 2008, Bouchard and Marino conjectured a recursion relation convenient to compute those Hurwitz numbers of fixed topology. We propose two proofs: one based on Burnside's formula giving the generating function of Hurwitz numbers as a sum over partitions, which we convert into a matrix integral. A second proof is based on Goulden and Jackson's cut and join equations, which construct ramified coverings of the sphere inductively.
Families enumerated by the so-called Baxter numbers appear recurrently in combinatorics. These families, which include plane bipolar orientations and certain dissections of a rectangle, exhibit always the same generating tree that has a simple form involving two catalytic parameters. We show here bijections between different Baxter families. A specialization of one bijection ensures that rooted non-separating maps correspond to certain pattern-avoiding permutations, recovering a result by Dulucq, Gire, and West.
In 1986 Bender and Canfield showed that the number of $n$-edge rooted maps on an orientable surface of genus $g$ is asymptotic to $$t_g n^{5(g-1)/2}12^n,~n\to \infty,$$ where $t_g$ depends only on $g$. Later it was shown that many families of maps satisfy similar asymptotic formulas in which $t_g$ appear as ``universal constants''. For over twenty years, the constants $t_g$ remained hard to compute or estimate partly due to the complexity of their nonlinear recursion. In this talk, we will describe how a simple recursion is derived for $t_g$ based on a new recursion for the number of triangulations recently derived by Goulden and Jackson. We will also describe the mysterious connections between $t_g$ and other combinatorial structures, and with Painleve I ODE. As a result, an asymptotic formula for $t_g$ can be derived and it is used by Garoufalidis, L\^{e}, and Mari\~{n}o to prove a long standing conjecture of $'$t Hooft about analyticity of free energy.
Maps in an orientable surface of arbitrary genus and branched covers of the sphere can both be represented by factorizations in the symmetric group, in which the subgroup generated by the factors acts transitively on the underlying symbols (these are called "transitive factorizations"). The generating series for a large class of transitive factorizations satisfies the KP hierarchy. We shall discuss the KP hierarchy and a new algebraic combinatorial proof of the fundamental result that relates Schur function expansions of a solution and the Plucker relations. As an application, we give a recurrence for triangulations of a surface of arbitrary genus obtained from the simplest partial differential equation in the KP hierarchy. The recurrence is very simple, but we do not know a combinatorial interpretation of it, yet it leads to precise asymptotics for the number of triangulations with n edges, in a surface of genus g.
We describe numerical simulations of spin models on planar random graphs and their interest from the point of view of disordered systems. The standard analytical approach in such models describes annealed (geometrical) disorder, where the graph is changing on the same timescale as the spins, but it is also possible to consider quenched disorder, where the graphs are "frozen". The latter serves as a test of the Harris-Luck crierion for the relevance of disorder to changing the critical exponents of a phase transition. A puzzle is that in the quenched case a naive application of the replica trick predicts critical exponents which are in disagreement with simulations. A further wrinkle that may be added to such simulations is to consider anti-ferromagnetic models, both on annealed and quenched ensembles of graphs, and we discuss results from these too.
Since the seminal work of Erd{\H o}s and R\'enyi the phase transition of the largest components in random graphs became one of the central topics in random graph theory and discrete probability theory. Of particular interest in recent years are random graphs on a surface, in particular random planar graphs.
We consider a uniform random planar graph $P(n,M)$, a graph picked uniformly at random among all graphs on vertex set $[n]$ with $M$ edges that are embeddable in the plane. We observe two critical behaviour of the largest components in $P(n,M)$: when $M=n/2+o(n)$ with scaling window of size $n^{2/3}$, and when $M=n+o(n)$ with scaling window of size $n^{3/5}$. For example, when $M=n/2+s$ for $n^{2/3}\ll s \ll n$, with probability tending to 1 as $n\to \infty$ the largest component in $P(n,M)$ is of size $(2+o(1))s$, whereas when $M=n+t$ for $n^{3/5}\ll t \ll n$, with probability tending to 1 as $n\to \infty$ the number of vertices outside the giant component is $\Theta(n^{3/2}t^{-3/2})$.
This is joint work with Tomasz {\L}uczak.
Rooted planar quadrangulations can be represented (bijectively) by certain well-labeled trees. Under this representation the tree depends in an essential way on the choice of a root in a quadrangulation. We consider this dependency and show that in the case of a uniform infinite quadrangulation, a finite displacement of the root results in only a finite modification to the corresponding well-labelled tree. The proof relies on a construction of certain trees of geodesics.
The Brownian map is the conjectured scaling limit of large random planar maps, in the sense of the Gromov-Hausdorff distance between compact metric spaces. We will discuss the known convergence results towards the Brownian map. We will then present some properties of this random metric space. In particular, we will completely describe the geodesics from the distinguished point called the root, and we will explain the implications of this result for geodesics in typical large planar maps.
It is a classical conjecture of discrete math that each cubic bridgeless graph has an exponential number of perfect matchings. I will introduce the problem, speak about the recent new proof of L. Gurvits for bipartite graphs (the original proof is by A. Schrijver) and about the case of the planar graphs, which was settled recently by M. Chudnovska and P. Seymour (using 4ColorTheorem).
Then I will discuss our reformulation by counting satisfying states of the Ising model on the triangulations of orientable surfaces. In this way the problem seems to be suitable to the transfer matrix treatment, and I will present first results towards this goal.
This is joint work with Andrea Jimenez.
We discuss asymptotics of large random maps in which the distribution of the degree of a typical face has a polynomial tail. When the number of vertices of the map goes to infinity, the appropriately rescaled distances from a base vertex can be described in terms of a new random process, defined in terms of a field of Brownian bridges over the so-called stable trees.
This allows to obtain weak convergence results for these "maps with large faces", viewed as metric spaces by endowing the set of their vertices with the graph distance. The limiting spaces form a one-parameter family of "stable maps", in a way parallel to the fact that the so-called Brownian map is the conjectured scaling limit for families of map, in which faces have degrees with exponential tails. This work takes part of its motivation from the study of statistical physics models on random maps.
This is joint work with J.-F. Le Gall.
Given a class $\cal A$ of graphs, let ${\cal A}_n$ denote the set of graphs in the class on vertex set $1,..,n$. Call $\cal A$ {\em smooth} if $|{\cal A}_n| / (n |{\cal A}_{n-1}|$ tends to a limit as $n \to \infty$. Also, let the {\em core} of a graph be the unique maximal subgraph with minimum degree at least 2. We follow a more combinatorial version of the approach of Bender, Canfield and Richmond (2008) to show that labelled graph classes with certain properties are smooth, and find information on the typical behaviour of the core, for example the typical proportion of vertices in the core. These results apply in particular to the class of graphs embeddable on a given surface.
We show that the number of labelled graphs with $n$ vertices that can be embedded in the orientable surface $S_g$ of genus $g$ grows asymptotically like $$ c^{(g)}n^{5(g-1)/2-1}\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 obtained by Giménez and Noy. We prove an analogous result for non-orientable surfaces, and we show that several parameters of interest behave asymptotically as in the planar case. In particular, we prove that a random graph embeddable in $S_g$ has a unique 2-connected component of linear size with high probability, and we show that the size is distributed in the limit as an Airy law of the map type.
This is joint work with Guillaume Chapuy, Eric Fusy, Omer Giménez and Bojan Mohar.
Random matrix theories allow to study some generating functions of colored (or non-colored) maps. In particular, there exists a very simple recipe allowing to establish constraints on these generating functions: the so-called loop equations, which are nothing but a rewriting of Tutte's equations. I will present a recursive method to solve these equations in the case of bi-colored maps, following an idea introduced by Eynard for the enumeration of non-colored maps. This topological recursion allows to compute the generating function of bi-colored tessellations of surfaces of arbitrary topology by induction on the Euler characteristic of the latter. Based on joint works with L. Chekhov and B. Eynard.
This talk is devoted to the study of the typical structure of a random map. Particularly, we investigate the degree sequences of random maps from families of a certain type, which, among others, includes fundamental map classes like those of biconnected maps, 3-connected maps, and triangulations. In particular, we develop a general framework that allows us to derive relations and exact asymptotic expressions for the expected number of vertices of degree k in random maps from these classes, and also provide accompanying large deviation statements. As concrete results of our framework we obtain precise information about the number of vertices of degree k in random biconnected, 3-connected, loopless, and bridgeless maps.
We consider the asymptotic behaviour of the terms in sequences satisfying recursions of the form $$a_{n} = a_{n-1} + \sum_{k = d}^{n - d} f(n, k)a_{k}a_{n - k},$$ where $f(n, k)$ behaves like a product of reciprocals of binomial coefficients. One application is to the map constants $t_{g}$ of Bender and Canfield, another to the Airy constants studied by P. Flajolet and G. Louchard, and some recurrences connected to Ricatti equations and Painlev\'{e} I equations. Jason Gao will describe the asymptotics of the $t_{g}$ with much greater precision.
This is joint work with Ed Bender, A. Olde Dalhuis, Jason Gao, and Nick Wormald.
Consider a family $\mathcal{T}$ of $3$-connected graphs of moderate growth, and let $\mathcal{G}$ be the class of graphs whose $3$-connected components are graphs in $\mathcal{T}$. We present a general framework for analyzing such graphs classes based on singularity analysis of generating functions, which generalizes previously studied cases such as planar graphs and series-parallel graphs. We provide a general result for the asymptotic number of graphs in $\mathcal{G}$, based on the singularities of the exponential generating function associated to $\mathcal{T}$. We derive limit laws, which are either normal or Poisson, for several basic parameters, including the number of edges, number of blocks and number of components. For the size of the largest block we find a fundamental dichotomy: classes similar to planar graphs have almost surely a unique block of linear size, while classes similar to series-parallel graphs have only sublinear blocks. This dichotomy also applies to the size of the largest 3-connected component. For some classes under study both regimes occur, because of a critical phenomenon as the edge density in the class varies. This is a joint work with Omer Giménez and Marc Noy.