Programme du little workshop

Enumerative topology and random discrete structures

Retour à la page principale.

Orateurs: O. Angel (Toronto), N. Broutin (Montréal), J. Bouttier (Saclay), B. Eynard (Saclay), I. Gessel (Brandeis), T. Guttmann (Melbourne), M. Krikun (Nancy), J.F. Le Gall (Paris), S. Vidal (Lille), N. Wormald (Waterloo)

Soit 10 exposés de 50 minutes + questions.



Amphi Jean Perrin du Laboratoire de Chimie physique (ground floor of the building right in front of the IHP, always inside the Marie Curie Campus, number 4 on the map).


Amphi Hermite of the IHP.

J. Bouttier, Counting maps with trees, for fun and profit.
I will review a number of bijections relating planar maps to trees, that were first devised as elementary combinatorial proofs for many map enumeration results alternatively found by more involved techniques (typically requiring to "solve" Tutte equations or matrix models), but then turned out to have interesting applications in the study of random maps.

O. Angel, Recurrence of weak graph limits.
A result of Benjamini and Schramm states that the weak limit of a sequence of planar graphs with uniformly bounded degrees is a.s. recurrent. We extend this results to limits of graphs excluding (any) fixed minor. Joint with Balazs Szegedy.

N. Wormald, Enumeration of unrooted planar maps.
I will discuss various aspects of the enumeration of unrooted planar maps. This will include both exact and asymptotic results, and in particular some description of how to efficiently enumerate unrooted 3-connected planar maps (i.e. unlabelled 3-connected planar graphs).

N. Broutin, Heights of random trees: towards unification.
(Joint work with L. Devroye, E. McLeish, and M. De la Salle)
Problems related to lengths of paths in trees appear in applications of Computer Science (analysis of algorithms), theoretical physics (first passage percolation), and probability (branching random walks). We aim at studying the random trees of logarithmic height in a unified way. For this class of trees, laws of large numbers for depths and heights in random trees can be obtained using an embedding using branching random walks and large deviations. However, some classes of trees, like most kinds of increasing trees, cannot be constructed using the latter embedding. To cope with this issue, we introduce a model based on a generalized branching random walk that premits to capture more many new kinds of trees. We will review classical examples using this approach, and will describe how the framework can be used to obtain various new results explaining the structure of random trees.

M. Krikun, Triangulations with multiple boundaries.
The combinatorial (i.e. not involving matrix integrals) methods of map enumeration, when applied to maps on surfaces of higher genera, lead naturally to the problem of enumeration for surfaces with multiple holes. I will remind the general method and related results, and then concentrate on a simpler example -- certain class of triangulations, where the exact formulas can be obtained in the planar case. Finally, I will discuss possible applications of this result.

J.F. Le Gall, La limite continue des grandes cartes planaires aléatoires.
L'ensemble des sommets d'une carte planaire, muni de la distance de graphe, est un espace métrique fini. Si on choisit la carte planaire au hasard parmi les cartes à n faces dans une classe convenable, et si on renormalise la distance par le facteur n^{-1/4}, on conjecture que l'espace métrique aléatoire obtenu converge en loi vers un espace métrique compact aléatoire parfois appelé la carte brownienne. Une premiére version de cette convergence a été obtenue par Marckert et Mokkadem dans un sens faible et pour le cas des quadrangulations. Nous discutons des progrés récents concernant le cas de cartes biparties et traitant la convergence au sens de la métrique de Gromov-Hausdorff utilisée par les géométres. En application, nous montrons que toute limite continue des grandes cartes planaires aléatoires est de dimension de Hausdorff 4 et homéomorphe a la sphére de dimension deux.

B. Eynard, Number of maps of any genus, algebraic geometry and integrable hierarchies.
Using formal matrix integrals, it is possible to write recursion relations called loop equations (Tutte's equations for the simplest cases) for counting various types of maps (arbitrary face degrees, possibly bi-colored, with boundaries,...). We present the solution (for any genus), in terms of algebraic geometry invariants of a rational spectral curve, i.e. residues of rational functions. Moreover, the algebraic invariants of that spectral curve satisfy an integrable hierarchy (multicomponent KP). The solution also allows to find the "continuum limits" of map numbers.

I. Gessel Is Analysis Necessary?
Abstract: Analytic techniques can be used to prove results, such as combinatorial identities or theorems about formal power series, whose statement involves no analysis. I will discuss the question of whether analysis is really necessary to prove such results, with examples involving integration, residues, P-recursive sequences, and asymptotic series.

S. Vidal, Combinatorial Maps, Modular Group and the Airy Function.
We shall present some recent results in exact enumeration of unrooted maps. They use as a major ingredient, the theory of combinatorial species due to Joyal and the combinatorics school of Montreal. Incidentally, those enumeration results, revealed a exciting new connection with the asymptotic of the Airy function. We shall give a precise statement and a combinatorial proof of it. The method of proof is combinatorial in that it use an interesting recursive decomposition of pointed triangular maps. The immediate application of this recursive decomposition are, a simple and optimal algorithm of exhaustive generation and an unbiased random sampler. In the introduction we shall insist on the group-theoretic aspects of combinatorial maps which are the main feature of our approach.

T. Guttmann, Area Distribution and Scaling Functions for Polygons.
In joint work with Christoph Richard and Iwan Jensen, we study the area distribution and scaling function of self-avoiding polygons "punctured" by holes which are also self-avoiding polygons. Similarly for staircase polygons, punctured by staircase polygonal holes. We prove some theorems, conjecture some exact results, provide extensive numerical support for our conjectures, and discuss limit distributions and scaling functions.