Coalescence: Emergence of the Map--Airy Law

Cyril Banderier

Algorithms Project, INRIA Rocquencourt

Algorithms Seminar

March 20, 2000

[summary by Michel Nguyen-The]

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
Maps are planar graphs presented together with an embedding in the plane, and as such, they model the topology of many geometric arrangements. This talk is concerned with the statistical properties of random maps, and focuses on connectivity issues. The analysis that we introduce is largely based on a method of ``coalescing saddle points.'' We exhibit here a new class of ``universal'' phenomena that are of the exponential-cubic type exp ix3, corresponding to nonstandard distributions that involve the Airy function. Consequences include the analysis and fine optimization of random generation algorithms for multiply connected planar graphs.

(Joint work of C. Banderier with P. Flajolet, G. Schaeffer and M. Soria.)



1   Statistical Properties of Random Maps

Generically, M and  C will be two classes of maps, respectively the ``basic maps'' and the ``core-maps,'' with Mn and  Cn the subsets of elements of size n. Here, the class  C is always a subset of  M satisfying additional properties, such as higher connectivity.

1.1   Combinatorics of maps

Let Mn and Ck be the cardinalities of Mn and Ck. The generating functions of M and C are respectively defined by M(z)=ån³1 Mn zn and C(z)=åk³1Ckzk.

(i)  Root-face decomposition. From the quadratic method [6, Sec. 2.9] and from root-face decomposition [9], one can find two power series y and f, such that M(z)=y(L(z)), where L is implicitly determined by L(z)=zf(L(z)). For nonseparable maps, one has f(y)=(1+y)3 and y(y)=y(1-y). Lagrange inversion theorem [6] hence yields:
Mn=[zn]M(z) =
1
n
 [yn] y'(y) f(y)n, that is, for nonseparable maps: Mn=
4(3n)!
n! (2n+2)!
.

(ii)  Substitution decomposition. Noticing that the generating functions z+2M(z)2/1+M(z) and C(M(z)) enumerate respectively the maps without core (i.e., no submap that is element of  Cn) and the maps formed of a nondegenerate core in which maps are substituted, we deduce that M(z) satisfies [9]:
M(z)= æ
ç
ç
è		 z+
2M(z)2
1+M(z)
ö
÷
÷
ø		 +C ( M(z) ) .

Define the bivariate generating function M(z,u)=ån,k Mn,kuk zn, with Mn,k=Card Mn,k, where Mn,k is the set of maps of size n having a core of k+1 edges. Tutte proved the refinement M(z,u)=C(uM(z)).

1.2   Connectivity issues

We are interested in the probability P[Xn=k] that a map of Mn has a core with k+1 edges. This probability is given by
P[Xn=k]=
Ck [zn]M(z)k
Mn
,   with   [zn]M(z)k =
k
n
 [yn-1]yy'(y)y(y)k-1f(y)n,
where the second equality results from Lagrange inversion.

1.3   The asymptotics of maps

Thanks to transfer methods [4], one can derive asymptotics for Mn and Ck [1]. One obtains positive numbers b and b', as well as r and t, such that as n®¥:

Mn ~
3b
4(p)1/2
 
r-n
n5/2
,   in particular    M
(non sep.)
 
n
~
(3)1/2
2(p)1/2
æ
ç
ç
è
27
4
ö
÷
÷
ø
n



 
n-5/2;
Ck ~
3b'
4(p)1/2
  y(t)-kk-5/2,   in particular    C
(3-conn.)
 
k
~
8
243(p)1/2
4k k-5/2.

Hence, studying P[Xn=k] essentially consists in estimating [zn]M(z)k.

2   Two Saddle Points

Let us start the estimation of [zn]M(z)k by Cauchy's formula,
[zn] Mk(z)=
k
n
1
2ip
ó
õ
 


G
z ( y(z)k ) ' f(z)n
dz
zn+1
=
k
n
1
2ip
ó
õ
 


G
G(z)  y(z)k ( f(z)/z )
n
 
 
 dz
where G is a contour encircling the origin and G(z)=y'(z)/y(z)=(1-2z)/(z(1-z)).

We make use of the saddle-point method. The idea consists in deforming the contour G in the complex plane in order to have it cross a saddle point of the integrand f (i.e., a zero of the derivative) and to take advantage of concentration of the integral near the saddle point.

The problem at hand furnishes with two saddle points, z+=1/2 and z-=(n-k)/(n+k), solutions of the equation / z(klny+nln(f/z))=0. We distinguish four cases.

2.1   Distinct saddles

When k<n/3, the saddle point z+=1/2 is dominant, and when k>n/3, z-=(n-k)/(n+k) dominates. If k is far enough from n/3, the basic saddle-point method applies and we use for contour a circle G0 centered around the origin and passing through the dominant saddle point t. Local expansions are of the ``exponential quadratic'' type and, the contour being orthogonal to the real axis in t, the real-variable Laplace method permits one to estimate the integral asymptotically [3]. Then we have:
Theorem 1  [Tails and distinct saddles [5]]   Let l(n) be an arbitrary function with l(n)®+¥ and l(n)=o(n1/3). Then, the probability distribution of the core of random element of Mn satisfies
P[Xn=k]~
32
243(p)1/2
·
n5/2
k3/2(n-3k)5/2
, uniformly for l(n)<k<
n
3
-n2/3l(n);
P[Xn=k]=O ( exp(-n(k/n-1/3)3) ) , uniformly for k>
n
3
+n2/3l(n).

2.2   A double saddle

Here we directly attack the analysis of the ``center'' of the distribution, that is, the case where n=3k exactly. Then, the saddle points become equal: z-=z+=t. The function f can be written f(z)=f(t)+f(3)(t)(z-t)3/6 +O((z-t)4), with f(3)(t) real and negative. Hence the curves of steepest descent, corresponding to real and nonpositive f(3)(t)(z-t)3/6 when z is close to t, either follow the positive real axis or form an angle of ±2p/3 with it. We approximate those last two curves by replacing a small arc of G0 by two small segments D1 and D2 intersecting t at an angle of ±2p/3. A few computations then deliver:
P[X3k=k]=
4
27
G(2/3)
31/6p
k-2/3 ( 1+O ( (ln k)4k-1/3 ) ) ,   with  
4
27
G(2/3)
31/6p
» 0.0531.
The estimation remains valid for n=3k+1 and n=3k+2. A similar result holds for n=3k+O(1).

2.3   Nearby saddles

When k is close to n/3, we choose a contour G with the same shape as previously but going through the mid-point z:=(z-+z+)/2, so that it simultaneously catches the contributions of the two saddle points z- and z+. Local estimates of the integrand lead to an expression involving Airy functions. With the ``map--Airy'' distribution A defined by
A(x)=2exp æ
ç
ç
è		 -
2
3
x3 ö
÷
÷
ø		 ( xAi(x2)-Ai'(x2) ) , where Ai(z)=
1
2p
ó
õ
+¥


-¥
e
i(zt+t3/3)
 
 dt,
we have indeed: supa£ k-n/3/n2/3£ b |n2/3 P[Xn=k]-16/8134/3/4 A(34/3/4k-n/3/n2/3)| ¾®0. as n®¥.

2.4   Coalescing saddles

This case is an improvement of the former one, in so far as we provide a uniform description of the transition regions around n/3, allowing k to range anywhere between l(n) and n-l(n), for any l(n)=o(n) with l(n)®¥. We set k=(1/3+b)n, and make b vary in any compact subinterval of (-1/3,2/3). By a change of variable, one reduces the computation to the case of (the exponential of) a cubic integrand [1, 2, 10]---the simplest case enabling a double saddle point--- to get:
P[Xn=n/3+b n]=
16
81(1+3b)3/2n2/3
æ
ç
ç
è
a1
2
A(c)+
a4
n2/3
exp æ
ç
ç
è		 -
2
3
c3 ö
÷
÷
ø		 Ai(c2) ö
÷
÷
ø		 ( 1+O(1/n) ) ,
where: (i) c=n1/3g; (ii) the error term is uniform for b in any compact subinterval of (-1/3,2/3) and is also uniform for any k>l(n), up to replacing O(1/n) with O(l(n)-1); (iii) g, a1, a4 are functions of b made explicit in [1].

3   Applications to Maps and Random Sampling

Maps ( M), Mn Cores ( C), Scheme a0 c
general, n edges 1, M~ C[ X M2] 1/3 3/42/3
general, n edges bridgeless, M~ C[ X( X M)*] 4/5 (5/3)2/3/4
general, n edges loopless, M~ L+ C[ X(( X M)*)2] 2/3 3/2
loopless , n edges simple, M~ C[ X M] 2/3 34/3/4
bipartite, n edges bipartite simple, M~ C[ X M] 5/9 38/3/20
bipartite, n edges bipartite nonseparable, M~ C[ X M2] 5/13 (13/6)5/3·3/10
bipartite, n edges bipartite bridgeless, M~ C[ X( X M)*] 3/5 (15/2)5/3/18
nonseparable, n edges simple nonseparable, M~ C[ X M] 4/5 155/3/36
nonseparable, n+1 edges 3-connected, M~ D+ C[ M] 1/3 34/3/4
cubic nonseparable, n+2 faces cubic 3-connected, M~ C[ X(1+ M)3] 1/2 (3/2)1/3
cubic 3-connected, n+2 faces cubic 4-connected, M~ M· C[ X M2] 1/2 62/3/3

Table 1: A selection of composition schemes ( X an edge, L,  D auxiliary families).

The former framework was applied to the families of random maps presented in Table 1, whose generating functions are all of Lagrangian type. Each family is characterized by two parameters a0 and c, displayed in Table 1.

Theorem 2   Consider any scheme of Table 1 with parameters a0 and c. The probability P[Xn=k] that a map of size n has a core of size k has a local limit law of the map--Airy type with centering constant a0 and scale parameter c.

Suppose now that one wants to generate a random map from a given family in Table 1. For general, nonseparable, bipartite, and cubic nonseparable maps, an algorithm Map is already given in [8] that takes an integer n and outputs in linear time a map of size n uniformly at random. For the other families of Table 1, one can use the following probabilistic algorithm Core(k) with parameter f(k):
  1. use Map(n) to generate a random map MÎ M of size n=f(k);
  2. extract the largest component C of M with respect to the scheme;
  3. if C does not have size k, then go back to step 1; otherwise output C.
Except for an exponentially small number of failures, this algorithm produces an element of Ck with uniform probability. Among other results, we have:

Theorem 3   In all extraction/rejection algorithms of [8], the choice f(k)=k/a0 yields an algorithm whose average number of iterations satisfies
ln~ n2/3/ ( A(0)c ) .
Let x0» 0.44322 be the position of the peak of the map--Airy density function given by the equation
(1-4x03)Ai(x02)+4x02Ai'(x02)=0.
The optimal choice f(k)=k/a0-(x0/a0c) (k/a0)2/3 reduces the expected number of loops by 1- A(0)/ A(x0)»30%.
This proves that the extraction/rejection algorithms have overall complexity O(k5/3), as do variant algorithms of [7, 8] that are uniform over all  Ck. This complexity drops to O(k) if one allows some small tolerance on the size of the generated map.

References

[1]
Banderier (Cyril), Flajolet (Philippe), Schaeffer (Gilles), and Soria (Michèle). -- Planar maps and Airy phenomena. In Montanari (Ugo), Rolim (José D. P.), and Welzl (Emo) (editors), Automata, languages and programming. Lecture Notes in Computer Science, vol. 1853, pp. 388--402. -- Springer, New York, 2000. Proceedings of the 27th ICALP Conference, Geneva, Switzerland, July 2000.

[2]
Bleistein (Norman) and Handelsman (Richard A.). -- Asymptotic expansions of integrals. -- Dover Publications Inc., New York, 1986, xvi+425p. A reprint of the second Holt, Rinehart and Winston edition, 1975.

[3]
de Bruijn (N. G.). -- Asymptotic methods in analysis. -- Dover Publications Inc., New York, 1981, third edition, xii+200p. A reprint of the third North Holland edition, 1970 (first edition, 1958).

[4]
Flajolet (Philippe) and Odlyzko (Andrew). -- Singularity analysis of generating functions. SIAM Journal on Discrete Mathematics, vol. 3, n°2, 1990, pp. 216--240.

[5]
Gao (Zhicheng) and Wormald (Nicholas C.). -- The size of the largest components in random planar maps. SIAM Journal on Discrete Mathematics, vol. 12, n°2, 1999, pp. 217--228.

[6]
Goulden (I. P.) and Jackson (D. M.). -- Combinatorial enumeration. -- John Wiley & Sons Inc., New York, 1983, xxiv+569p. With a foreword by Gian-Carlo Rota, Wiley-Interscience Series in Discrete Mathematics.

[7]
Schaeffer (Gilles). -- Conjugaison d'arbres et cartes combinatoires aléatoires. -- PhD thesis, Université Bordeaux I, 1998.

[8]
Schaeffer (Gilles). -- Random sampling of large planar maps and convex polyhedra. In Proceedings of the thirty-first annual ACM symposium on theory of computing (STOC'99). pp. 760--769. -- ACM press, Atlanta, Georgia, may 1999.

[9]
Tutte (W. T.). -- Planar enumeration. In Graph theory and combinatorics (Cambridge, 1983), pp. 315--319. -- Academic Press, London, 1984.

[10]
Wong (R.). -- Asymptotic approximations of integrals. -- Academic Press Inc., Boston, MA, 1989, xiv+546p.
This document was translated from LATEX by HEVEA.