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 hn( 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 ( hn( T)>cn ) >1-exp
-d n
 
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 hn( T) is sharply concentrated around cn for some constant c. More precisely:

Theorem 1   Let T be a 3-connected 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(|hn( T)-cn|=o(cn))®1.

A near-triangulation is composed of triangulations except that it can have more than 3 vertices on its external face. Define
µk=
8(k-2)
4k2-1
æ
ç
ç
è		 -
3
4
ö
÷
÷
ø
k



 
æ
è
-3/2
k
ö
ø
.

Theorem 2   Let M be a 3-connected near-triangulation 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 ( | hn( M)-r µk(27/256)j-1 n | =o(n) ) ® 1.



Proof. The method used here relies on Chebyshev-like inequalities: P(X>tµ)£1/t and P(|X-µ|³ ts)£1/t2 for a nonnegative random variable X with average µ and variance s2. A consequence is that if s=o(µ), then one gets a concentration result.

Let us first study the number zn(k) of vertices of degree k in a random triangulation with n+2 vertices. The quantity Tn denotes the number of rooted triangulation with n+2 vertices; Tn,k denotes the number of rooted triangulation with n+2 vertices and root vertex of degree k; Tn,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 [ zn(k) ] =
6n
k
Tn,k
Tn
    and     E [ zn(k)(zn(k)-1) ] =
6n
k
Tn,k,k
Tn
.

Step 2: Obtain functional equations for the generating functions for Tn,k,l, Tn,k, and Tn, 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):
Tn=(6)1/2/(32(p)1/2) n-5/2 (256/27)n ( 1+O(1/n) ) ,
Tn,k=
k(6)1/2
192 (p)1/2
µk n-5/2 (256/27)n ( 1+O(k20/n) ) ,
Tn,k,k=
k(6)1/2
192 (p)1/2
µk2 n-3/2 (256/27)n ( 1+O(k20/n) ) .

Step 4: Derive asymptotics for the first two moments of zn(k);
E [ zn(k) ] =nµk ( 1+O(k20/n) )     and     Var [ zn(k) ] =nµk+(nµk)2O(k20/n),
uniformly for k=O(ln n). It follows from Chebyshev's inequality that
P ( | zn(k)-µkn | =o(µkn) ) ®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 3-connected near-triangulation with j+3 vertices such that j is o(n) and that there are r distinct ways to root  T. Let hn( T) be the number of copies of T in a random rooted triangulation with n+2 vertices. Then
E [ hn( T) ] =r æ
ç
ç
è
27
256
ö
÷
÷
ø
j-1



 
E [ zn+1-j(3) ] ( 1+o(1) ) ,
E [ hn( T) (hn( T)-1) ] =r2 æ
ç
ç
è
27
256
ö
÷
÷
ø
2j-2



 
E [ zn+2-2j(3)(zn+2-2j(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 (y1,y2,...,yd). Define:
D(e,f)= {  x such that |x|£1+e, x¹1, |Arg(x-1)|³f  } ,
R(e,f)= ì
í
î		  (x,
_
y
 
) such that |yj|<1, 1£ j£ d, xÎD(e,f)  ü
ý
þ		 .

Let bj>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~((1-x)-aÕj=1d (1-yj)-bj) 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(|1-x|-aÕj=1d(1-|yj|)-bj) as (1-x)(1-yj)-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(|1-x|-a'Õj=1d(1-|yj|)-q).

Definition 2  [» notation]   We write f(x,y_)» c (1-x)-a Õj=1d (1-yj)-bj if f(x,y_) can be expressed as f(x,y_)=c(y_)(1-x)-a Õj=1d (1-yj)-bj+åj=0dCj(x,y_)+E(x,y_) where C0(x,y_) is a polynomial in x, and for 1£ j £ d, Cj(x,y_) is a polynomial in yj and where E(x,y_)=O~(|1-x|-a'Õj=1d(1-yj)-bj') for some a'<a and bj'³ 0, 1£ j £ n and finally where c(y_)=c+O(åj=1d |1-yj|) and is analytic when y_ÎD(e,f)d, with c(1_)=c¹ 0.

Lemma 2   Suppose that
f(x,
_
y
 
)=
~
O
 
æ
ç
ç
è		 (1-x)
-a
 
d
Õ
j=1
(1-yj)
-bj
 
ö
÷
÷
ø		 ;
then as n®¥ and 1³ kj=O(ln n),
[xn
_
y
 
k]f(x,
_
y
 
)=O æ
ç
ç
è		 n
a-1
 
d
Õ
j=1
k
bj
 
j
ö
÷
÷
ø		 ;
and for any 0<e'<1 and for all n and kj,
[xn
_
y
 
k]f(x,
_
y
 
)=O æ
ç
ç
è		 n
a-1
 
d
Õ
j=1
(1-e')
bj
 
ö
÷
÷
ø		 .

Lemma 3   Let d³ 1 and f(x,y_)» c(1-x)-a Õj=1d(1-yj)-bj, where a is neither a negative integer nor 0, and c¹0. Then as n®¥ and kj=O(ln n),
[xn
_
y
 
k]f(x,
_
y
 
)=
c
G(a)
d
Õ
j=1
æ
ç
ç
è		 k
bj-1
 
j
/G(bj) ö
÷
÷
ø		 æ
ç
ç
è		 1+O æ
ç
ç
è
d
å
j=1
1/kj ö
÷
÷
ø		 ö
÷
÷
ø		 .

3   Maximum Vertex Degree

Let dn 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 n-gon,
P ( | dn-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

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 (Zhi-Cheng), and Richmond (L. Bruce). -- Submaps of maps. I. General 0--1 laws. Journal of Combinatorial Theory. Series B, vol. 55, n°1, 1992, pp. 104--117.

[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. 105--117.

[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. 201--230.

[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. 183--208.

[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. 194--211. -- 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. 61--71.
1
Philippe Flajolet coined this naming in reference to Borges's novel The Library of Babel.
This document was translated from LATEX by HEVEA.