Enlarged Logo[But only 10 vertices]

The above graph is an enlarged version of Andersen's logo. Although this graph is a complete static structure, it was created from scratch by successively adding random edges between the nodes of the graph. Thereby it relates to the area of random graphs, which was invented in 1960 by Erdös and Rényi ("On the Evolution of Random Graphs", Publ. Math. Inst. Hung. Acad. Sci., Vol. 5, pp. 17-67). This mathematical theory concerns the changes in the characteristics of a graph with a given number of nodes (also called vertices). A stochastic process is randomly adding branches (also called edges) to the graph. The process starts with the first branch between two randomly chosen nodes, and it stops when there is a branch between all pairs of nodes in the graph. This process is described in the idiosyncratic title of Palmer's book on the subject:

An important indicator of the properties of the random graph is the relation between the number of branches (K) and the number of nodes (N). If the K/N ratio is 0.1, most nodes are isolated. As in increases towards 0.5, the sizes of the connected components grows and their number decrease. Beyond 0.5, there is a rapid transition towards a single connected component.

Figure 1 shows the initial evolution of a random graph as more and more branches are added.

a. K/N = 0.15                 b. K/N = 0.35

c. K/N = 0.55                 d. K/N = 0.65

Figure 1: Steps in the evolution of a random graph.

Random := proc(N,K,seed)
local die,edge,G,q,success;
   if K/N > 2 then
      ERROR(`this procedure is unfit for high K/N ratios`); 
   fi;
   _seed := seed;
   G := new();
   addvertex({seq(i,i=1..N)},G);
   die := rand(1..N);
   for i from 1 to K do	success := false;
      while success <> true do
         edge := convert([die(),die()],set);
         if not member(edge, ends(G)) then
            if nops(edge) = 2 then
               addedge(edge,G);
               success := true;
            fi;
         fi;
      od;
   od;
   RETURN(G);
end:

==in=> Gr1 := Random(20, 3, 5); components(Gr1);
     =out=> {{11}, {1}, {5}, {6}, {7}, {9}, {10}, {12}, {13}, {14},
            {15}, {16}, {19}, {20}, {3, 4}, {2, 8}, {17, 18}}

==in=> Gr2 := Random(20, 7, 5); components(Gr2);
     =out=> {{7}, {9}, {12}, {13}, {15}, {16}, {20}, {17, 18},
            {6, 14}, {3, 4}, {10, 11}, {1, 19}, {2, 5, 8}}

==in=> Gr3 := Random(20, 11, 5); components(Gr3);
     =out=> {{16}, {13}, {7}, {12}, {20}, {3, 4}, {1, 19},
            {6, 14}, {2, 5, 8, 9, 10, 11, 15, 17, 18}}

==in=> Gr4 := Random(20, 15, 5); components(Gr4);
     =out=> {{16}, {13}, {12}, {20}, {1, 7, 19},
            {2, 3, 4, 5, 6, 8, 9, 10, 11, 14, 15, 17, 18}}

Although we are especially interested in the phase of graphical evolution where the nodes becomes gradually connected, the process will continue until any pair of nodes are connected by a direct branch.

==in=> Gr5 := random(20, prob=1); components(Gr5);
      =out=> {{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}}

==in=> nops(edges(Gr5));
      =out=> 190

==in=> draw(Gr5);
      =out=>

Figure 2: A complete [or "full"] random graph. K/N=9.5.

The analysis of the evolution of random graphs and related structures have been fairly wide-spread in relation to the study of complexity, e.g. at the Santa Fe Institute - cf. Stuart A. Kauffman (1993), The Origins of Order: Self-Organization and Selection in Evolution, New York and Oxford, Oxford University Press.

To inspect or run the Maple worksheet underlying this note, go to Andersen's Maple program page.