ANALYSIS of ALGORITHMS (Picture)

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]:


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);