Bruce Richmond
University of Waterloo
February 13, 2008
Title: Random maps
Abstract:
A map is a graph embedded on a surface, ie drawn on the
surface without
crossing edges. A planar map is a graph embedded on the
plane. We may
consider maps with n
>edges. A map is rooted when one edge, the root edge,
is distinguished and one vertex and one face incident with
the root edge are
distinguished. W. T. Tutte found that it is much easier to
count rooted maps
than maps. Counting 3-connected planar maps with n edges is equivalent
to counting 3-dimensional convex polyhedra with
n edges by a theorem of
Steinitz.
A copy of a map,M0,
in a map M is a
cycle of edges with M0
in the
interior of the cycle (loosely speaking). When we talk of
probabilities we
assume that the different maps with n edges are equally likely. A
‘useful’
fact is that for many families of maps (including connected,
2-connected, 3-connected, triangulations) almost all maps with n edges contain cn copies
of any particular planar element of the family. Tutte
constructed a 3 − c
planar map that is not Hamiltonian thereby disproving a
conjecture of P.
G. Tait. This example combined with the useful fact just
mentioned shows
that almost no 3 − c maps with n edges are Hamiltonian. These
results are
proved using results of E. Bender, R. Canfield, J. Gao, B.
Richmond, R. W.
Robinson and N. Wormald concerning the enumeration of maps
according to edges.
Recently maps have been enumerated according to the number
of vertices
by researchers in Britain, France and other countries. C. McDairmid has
shown for example that if the number of maps on a surface is
‘smooth’ then
the probability that a map with n
vertices is connected is ~ 0.9633
· · · and the
number of components is described by a Poisson distribution.
O. Gim´enez
and M. Roy have shown that the probability that a planar
graph is connected
is 0.96325· · ·. Recently E.
Bender, R. Canfield and B. Richmond have verified the smoothness property of McDairmid.
Benny Pinkas