ANALYSIS of ALGORITHMS (Picture)

This picture drawn under the Maple system for symbolic computations shows the behaviour in the complex plane of the generating function of connected graphs graphs counted according to number of nodes and edges. In critical regions, two saddle points coalesce giving rise to a so-called "monkey saddle" (a saddle that you'd use if you had three legs!!)

The fine analysis of this coalescence is crucial to the understanding of connectivity in random graphs and it relates to a famous series of problems initiated by Erdos and Renyi in the late 1950's. See the paper [Janson, Knuth, Luczak, Pittel: The birth of the giant component. Random Structures Algorithms 4 (1993), no. 3, 231--358] As said by Alan Frieze in his review [MR94h:05070]:

"This paper and its predecessor [MR90d:05184] mark the entry of generating functions into the general theory of random graphs in a significant way. Previously, their use had mainly been restricted to the study of random trees and mappings. Most of the major results in the area, starting with the pioneering papers of P. Erdos and A. Renyi [MR22#10924] have been proved without significant use of generating functions. However, at the early stages of the evolution of a random graph we find that it is usually not too far from being a forest, and this allows them an entry..."

The icon was generated by Maple code like this: f:=u^3/3-3*u+1; plots[complexplot3d]([Re(f),argument(f)],

u=-4-3*I..4+3*I,style=patchcontour, contours=30,numpoints=50*50);