Planar triangulations and a Brownian snake

Gilles Schaeffer

Loria -- CNRS, France

April 5,
refreshments at 3:45pm


A planar map is a proper embedding of a graph in the plane. W.T. Tutte gave in the 60's beautiful formulas for the number of (combinatorially distinct) planar maps with n edges but also for subclasses like triangulations, quadrangulations, etc. Some of these formulas were also found by physicists in the 70's. David Jackson recently discussed some algebraic aspects of this theory in this seminar (Feb. 20). We shall instead consider bijective approaches to enumerative and probabilistic questions.

First, I will present a bijective proof of Tutte's formulas, building on the cycle lemma used by Raney in his bijective proof of the Lagrange inversion formula. Second, following physicists, we shall put the uniform distribution on quadrangulations and view them as random surfaces. Bijections again allow to study the geometry of these random surfaces and lead to a surprising connection with a probabilistic process introduced by David Aldous (the Brownian snake constructed on a standard Brownian excursion). As a consequence the diameter (in graph theoretic sense) of a random quadrangulation with n vertices grows like n^{1/4}.

Speaker's Contact Info: Gilles.Schaeffer(at-sign)

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)

Page loaded on March 17, 2002 at 05:15 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.