Some Sharp Concentration Results about Random Planar
Triangulations
Jason Zhicheng Gao
School of Mathematics and Statistics, Carleton University
Algorithms Seminar
June 8, 2000
[summary by Cyril Banderier]
A properly typeset version of this document is available in
postscript and in
pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
Abstract
The theory of random maps has a relatively short history when compared
to the theory of random graphs. In this talk, we mention some recent
results concerning sharp concentration properties of parameters in
random planar triangulations. Examples include the maximum vertex
degree, the largest component, the number of copies of a given submap,
and the number of flippable edges. This is joint work by Jason
Zhicheng Gao and Nicholas Wormald (Melbourne, Australia).
1 Introduction
Draw a graph on a sphere and then mark (or ``root'') a face, an edge
of this face and a vertex of this edge. Then project the graph on the
plane (e.g., by a stereographic projection): you get a planar
map. Without loss of generality, you can rotate the sphere so that
the marked face contains the north pole; then the projection
transforms the marked face into an unbounded face, which is called the
external face.
For background, we refer to the summary of Gao's other talk
(pages ???? in these proceedings)
for several definitions and examples on maps and triangulations.
For ten years, Jason Zhicheng Gao (often collaborating with other
specialists of maps, namely Bender, Canfield, Richmond, McKay,
Wormald, ...) has studied several parameters of maps (strong
connexity, pattern occurrences, vertex degree, symmetries, cycles,
Eulerian properties), finding new functional equations, solving them,
and also obtaining precise asymptotic estimations. We specialize here
the discussion to two parameters that appear to be intimately related:
vertex degree and submap occurrence. Concentration results are
obtained by the second moment method.
2 Submap Density Result
Many combinatorial structures satisfy Borges's
Theorem,^{1} meaning that any
pattern will appear with high probability in a large enough structure.
Any word of length ln n appears with high probability in a random
word of length n (for more details, see the study by Guibas and
Odlyzko [6], and then by Nicodème et
al. [7, 8]). The occurrence of patterns in random
graphs has also been studied [2]. However for maps, the
situation is different as these objects live in quite a different
probability space. Let's make a bet: choose a map of size 6, while I
generate a random map of size 1000; would you bet that your map is a
submap of mine? This talk makes explicit the conditions under which
you can make good (or bad) bets.
Let T be any fixed triangulation and h_{n}( T)
be the random variable counting the number of
copies of T in a random triangulation with n vertices.
Richmond and Wormald [9] showed that
P 
( 
h_{n}( T)>cn 
) 
>1exp 

for some positive constants c and d depending on T.
Bender, Gao and Richmond [1] showed that the above result
holds for many families of maps, and recently Gao and
Wormald [4] proved that h_{n}( T) is sharply
concentrated around cn for some constant c. More precisely:
Theorem 1
Let T be a 3connected triangulation with j+3 vertices such that
there are r distinct ways to root T. Let c=2r(27/256)^{j}.
Then, provided that cn®¥,
P(h_{n}( T)cn=o(cn))®1.
A neartriangulation is composed of triangulations except that it can
have more than 3 vertices on its external face. Define
Theorem 2
Let M be a 3connected neartriangulation with external face of
degree k and with j internal vertices such that
there are r distinct ways to root the external face. Then, for fixed
j and k with k³4, one has
P 
( 
 
h_{n}( M)r µ_{k}(27/256)^{j1}
n 
 
=o(n) 
) 
® 1. 
Proof.
The method used here relies on Chebyshevlike inequalities:
P(X>tµ)£1/t and P(Xµ³ ts)£1/t^{2}
for a nonnegative random variable X with average µ and
variance s^{2}. A consequence is that if s=o(µ), then
one gets a concentration result.
Let us first study the number z_{n}(k) of vertices of degree k
in a random triangulation with n+2 vertices. The quantity T_{n}
denotes the number of rooted triangulation with n+2 vertices;
T_{n,k} denotes the number of rooted triangulation with
n+2 vertices and root vertex of degree k; T_{n,k,l} denotes
the number of rooted triangulation with n+2 vertices, root vertex of
degree k and another distinguished vertex of degree l. The scheme
of the proof is as follows:
Step 1: Use combinatorial arguments to show the relations
E 
[ 
z_{n}(k) 
] 
= 


and
E 
[ 
z_{n}(k)(z_{n}(k)1) 
] 
= 


. 
Step 2: Obtain functional equations for the generating
functions for T_{n,k,l}, T_{n,k}, and T_{n}, and perform
singularity analysis.
Step 3: Derive a suitable multivariate version of Flajolet
and Odlyzko's transfer theorem (see Lemmas 2 and 3 below), and obtain
the following asymptotics, uniformly for k=O(ln n):
T_{n}=(6)^{1/2}/(32(p)^{1/2}) n^{5/2} (256/27)^{n} 
( 
1+O(1/n) 
) 
, 
T_{n,k}= 

µ_{k} n^{5/2} (256/27)^{n}

( 
1+O(k^{20}/n) 
) 
, 
T_{n,k,k}= 

µ_{k}^{2} n^{3/2} (256/27)^{n}

( 
1+O(k^{20}/n) 
) 
. 
Step 4: Derive asymptotics for the first two moments of
z_{n}(k);
E 
[ 
z_{n}(k) 
] 
=nµ_{k} 
( 
1+O(k^{20}/n) 
) 
and
Var 
[ 
z_{n}(k) 
] 
=nµ_{k}+(nµ_{k})^{2}O(k^{20}/n), 
uniformly for k=O(ln n). It follows from Chebyshev's inequality that
P 
( 
 
z_{n}(k)µ_{k}n 
 
=o(µ_{k}n) 
) 
®1 
uniformly for k<(ln n(lnln n)/2)/ln(4/3)W(n).
The proof is based on three lemmas.
Lemma 1
Let T be a 3connected neartriangulation with j+3 vertices such
that j is o(n) and that there are r distinct ways to
root T. Let h_{n}( T) be the number of copies of T in a
random rooted triangulation with n+2 vertices. Then
E 
[ 
h_{n}( T) 
] 
=r 
æ ç ç è 

ö ÷ ÷ ø 

E 
[ 
z_{n+1j}(3) 
] 

( 
1+o(1) 
) 
, 

E 
[ 
h_{n}( T) (h_{n}( T)1) 
] 
=r^{2} 
æ ç ç è 

ö ÷ ÷ ø 

E 
[ 
z_{n+22j}(3)(z_{n+22j}(3)1) 
] 

( 
1+o(1) 
) 
. 

In order to state precise results, one needs the following notation:
let e be a small positive constant, f be a constant
satisfying 0<f<p/2, and y^{_} be (y_{1},y_{2},...,y_{d}). Define:
D(e,f)= 
{ 
x such that x£1+e,
x¹1, Arg(x1)³f 
} 
, 

R(e,f)= 
ì í î 
(x, 

) such that y_{j}<1, 1£
j£ d, xÎD(e,f) 
ü ý þ 
. 

Let b_{j}>0 for 1£ j£ d, and a be any real number.
The following two notations are also useful.
Definition 1 [O^{~} notation]
We write
f(x,y^{_})=O^{~}((1x)^{a}Õ_{j=1}^{d} (1y_{j})^{b}_{j})
if there exist e >0 and 0<f<p/2
such that, in R(e,f), f(x,y^{_}) is analytic and
f(x,y^{_})=O(1x^{a}Õ_{j=1}^{d}(1y_{j})^{b}_{j})
as (1x)(1y_{j})^{p}® 0, for 1£ j £ d, and some
p³ 0; for some q³ 0 and some real number a',
one has
f(x,y^{_})=O(1x^{a'}Õ_{j=1}^{d}(1y_{j})^{q}).
Definition 2 [» notation]
We write f(x,y^{_})» c (1x)^{a} Õ_{j=1}^{d}
(1y_{j})^{b}_{j} if f(x,y^{_}) can be expressed as f(x,y^{_})=c(y^{_})(1x)^{a} Õ_{j=1}^{d}
(1y_{j})^{b}_{j}+å_{j=0}^{d}C_{j}(x,y^{_})+E(x,y^{_}) where
C_{0}(x,y^{_}) is a polynomial in x, and for 1£ j £ d,
C_{j}(x,y^{_}) is a polynomial in y_{j} and where E(x,y^{_})=O^{~}(1x^{a'}Õ_{j=1}^{d}(1y_{j})^{b}_{j}^{'})
for some a'<a and b_{j}'³ 0, 1£ j £ n and
finally where c(y^{_})=c+O(å_{j=1}^{d} 1y_{j}) and is analytic
when y^{_}ÎD(e,f)^{d}, with c(1^{_})=c¹ 0.
Lemma 2
Suppose that
f(x, 

)= 

æ ç ç è 
(1x) 


(1y_{j}) 

ö ÷ ÷ ø 
; 
then as n®¥ and 1³ k_{j}=O(ln n),
[x^{n} 

^{k}]f(x, 

)=O 
æ ç ç è 
n 


k 

ö ÷ ÷ ø 
; 
and for any 0<e'<1 and for all n and k_{j},
[x^{n} 

^{k}]f(x, 

)=O 
æ ç ç è 
n 


(1e') 

ö ÷ ÷ ø 
. 
Lemma 3
Let d³ 1 and f(x,y^{_})» c(1x)^{a}
Õ_{j=1}^{d}(1y_{j})^{b}_{j}, where a is neither a negative
integer nor 0, and c¹0. Then as n®¥ and
k_{j}=O(ln n),
[x^{n} 

^{k}]f(x, 

)= 




æ ç ç è 
k 

/G(b_{j}) 
ö ÷ ÷ ø 
æ ç ç è 
1+O 
æ ç ç è 

1/k_{j} 
ö ÷ ÷ ø 
ö ÷ ÷ ø 
. 
3 Maximum Vertex Degree
Let d_{n} be the maximum vertex degree of a random map in a family of
maps of size n. Devroye, Flajolet, Hurtado, Noy, and
Steiger [3] showed that, for triangulations of an ngon,
P 
( 
 
d_{n}ln(n)/ln2 
 
£(1+e)lnln n/ln2 
) 
®1. 
Gao and Wormald [5] improved this last result and extended
it to general families of maps. They showed that, for any
function W going to infinity arbitrarily slowly, one has

for triangulations of an ngon:
P(d_{n}ln n +ln ln n/ln 2£
W(n))® 1,
 for 3connected triangulations of n vertices:
P(d_{n}ln n +(ln ln n)/2/ln (4/3)£
W(n))® 1,
 for all maps of n edges:
P(d_{n}ln n +(ln ln n)/2/ln (6/5)£
W(n))® 1.
4 A Few Open Problems
At the end of the talk, a few questions were raised, and
the following conjectures appear plausible but might involve hard
work.
Conjecture 1
The generating function of maps without a given submap is algebraic.
There is no doubt that a functional equation could be obtained for
each pattern (however, as the overlaps can be very intricate, the
functional equation would be horrendous, and it is not clear that a
generalization of the quadratic method would allow us to solve it, and
prove algebraicity).
Conjecture 2
A Gaussian limit law should hold.
Once more, we expect the behavior to be qualitatively the same for
words, trees and maps. Another interesting study (which is as of now
out of reach) is the occurrence of a given pattern, not in a local
sense but in a global one (such patterns are called ``minors'').
Other concentration results about random planar triangulations such as
the largest component and the number of flippable edges were finally
not presented in the talk but can be found in Gao's articles at his
homepage http://mathstat.math.carleton.ca/~zgao/
.
References
 [1]

Bender (Edward A.), Gao (ZhiCheng), and Richmond (L. Bruce). 
Submaps of maps. I. General 01 laws. Journal of
Combinatorial Theory. Series B, vol. 55, n°1, 1992,
pp. 104117.
 [2]

Bollobás (Béla). 
Random graphs. 
Academic Press Inc., London, 1985, xvi+447p.
 [3]

Devroye (L.), Flajolet (P.), Hurtado (F.), Noy (M.), and Steiger (W.). 
Properties of random triangulations and trees. Discrete &
Computational Geometry, vol. 22, n°1, 1999, pp. 105117.
 [4]

Gao (Zhicheng) and Wormald (Nicholas C.). 
Sharp concentration of the number of submaps in random planar
triangulations. 
Preprint.
 [5]

Gao (Zhicheng) and Wormald (Nicholas C.). 
The distribution of the maximum vertex degree in random planar maps.
Journal of Combinatorial Theory. Series A, vol. 89, n°2,
2000, pp. 201230.
 [6]

Guibas (L. J.) and Odlyzko (A. M.). 
String overlaps, pattern matching, and nontransitive games. Journal of Combinatorial Theory. Series A, vol. 30, n°2,
1981, pp. 183208.
 [7]

Nicodème (Pierre), Salvy (Bruno), and Flajolet (Philippe). 
Motif statistics. Theoretical Computer Science. 
To appear.
 [8]

Nicodème (Pierre), Salvy (Bruno), and Flajolet (Philippe). 
Motif statistics. In Nesetril (Jaroslav) (editor), Algorithms, ESA'99. Lecture Notes in Computer Science, vol. 1643,
pp. 194211. 
Springer, Berlin, 1999. Proceedings of the 7th Annual
European Symposium, Prague, Czech Republic, July 1999.
 [9]

Richmond (L. Bruce) and Wormald (Nicholas C.). 
Random triangulations of the plane. European Journal of
Combinatorics, vol. 9, n°1, 1988, pp. 6171.
 1
 Philippe Flajolet coined this naming in reference
to Borges's novel The Library of Babel.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.