Planar triangulations and a Brownian snakeGilles SchaefferLoria  CNRS, France
April 5,

ABSTRACT


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}. 
Combinatorics Seminar, Mathematics Department, MIT, sara(atsign)math.mit.edu 

