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 exponentialcubic type exp ix^{3}, 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.)
M_{n}=[z^{n}]M(z) = 

[y^{n}] y'(y) f(y)^{n}, that is, for nonseparable maps: M_{n}= 

. 
M(z)= 
æ ç ç è 
z+ 

ö ÷ ÷ ø 
+C  (  M(z)  )  . 
P[X_{n}=k]= 

, with [z^{n}]M(z)^{k} = 

[y^{n1}]yy'(y)y(y)^{k1}f(y)^{n}, 
M_{n} ~ 


, in particular  M 

~ 

æ ç ç è 

ö ÷ ÷ ø 

n^{5/2}; 
C_{k} ~ 

y(t)^{k}k^{5/2}, in particular  C 

~ 

4^{k} k^{5/2}. 
[z^{n}] M^{k}(z)= 


ó õ 

z  (  y(z)^{k}  )  ' f(z)^{n} 

= 


ó õ 

G(z) y(z)^{k}  (  f(z)/z  ) 

dz 
P[X_{n}=k]~ 

· 

, uniformly for l(n)<k< 

n^{2/3}l(n); 
P[X_{n}=k]=O  (  exp(n(k/n1/3)^{3})  )  , uniformly for k> 

+n^{2/3}l(n). 
P[X_{3k}=k]= 


k^{2/3}  (  1+O  (  (ln k)^{4}k^{1/3}  )  )  , with 


» 0.0531. 
A(x)=2exp 
æ ç ç è 
 

x^{3} 
ö ÷ ÷ ø 
(  xAi(x^{2})Ai'(x^{2})  )  , where Ai(z)= 

ó õ 

e 

dt, 
P[X_{n}=n/3+b n]= 

æ ç ç è 

A(c)+ 

exp 
æ ç ç è 
 

c^{3} 
ö ÷ ÷ ø 
Ai(c^{2}) 
ö ÷ ÷ ø 
(  1+O(1/n)  )  , 
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 a_{0} and c, displayed in Table 1.
Maps ( M), M_{n} Cores ( C), Scheme a_{0} c
general, n edges 1, M~ C[ X M^{2}] 1/3 3/4^{2/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 3^{4/3}/4 bipartite, n edges bipartite simple, M~ C[ X M] 5/9 3^{8/3}/20 bipartite, n edges bipartite nonseparable, M~ C[ X M^{2}] 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 15^{5/3}/36 nonseparable, n+1 edges 3connected, M~ D+ C[ M] 1/3 3^{4/3}/4 cubic nonseparable, n+2 faces cubic 3connected, M~ C[ X(1+ M)^{3}] 1/2 (3/2)^{1/3} cubic 3connected, n+2 faces cubic 4connected, M~ M· C[ X M^{2}] 1/2 6^{2/3}/3
Table 1: A selection of composition schemes ( X an edge, L, D auxiliary families).
l_{n}~ n^{2/3}/  (  A(0)c  )  . 
This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.