Random maps, coalescing saddles, singularity analysis, and airy phenomena

A considerable number of asymptotic distributions arising in random combina torics and analysis of algorithms are of the exponential-quadratic type, th at is, Gaussian. We exhibit a class of "universal" phenomena that are of th e exponential-cubic type, corresponding to distributions that involve the A iry function. In this article. such Airy phenomena are related to the coale scence of saddle points and the confluence of singularities of generating f unctions. For about a dozen types of random planar maps, a common Airy dist ribution (equivalently, a stable law of exponent 3/2) describes the sizes o f cores and of largest (multi)connected components. Consequences include th e analysis and fine optimization of random generation algorithms for a mult iple connected planar graphs. Based on an extension of the singularity anal ysis framework suggested by the Airy case. the article also presents a gene ral classification of compositional schemas in analytic combinatorics. (C) 2001 John Wiley & Sons, Inc.