You are currently browsing the daily archive for 21 April, 2010.

Caption – 1st page of *Erdös*, P.; *Rényi*, A. (1960). “*On The Evolution of Random Graphs*“. *Magyar Tud. Akad. Mat. Kutató Int. Közl.* **5**: 17 [PDF].

Documentary film – “*N is a Number*: A Portrait of *Paul Erdös*” directed by George Csicsery | 1993 | 57 min. (9 parts)

“** There are three signs of senility. The first sign is that a man forgets his theorems. The second sign is that he forgets to zip up. The third sign is that he forgets to zip down**“,

*Paul Erdös*.

Paul* Erdös* was an immensely prolific and notably eccentric Hungarian mathematician. *Erdös *published more papers than any other mathematician in history, working with hundreds of collaborators. He worked on problems in combinatorics, graph theory, number theory, classical analysis, approximation theory, set theory, and probability theory. He wrote around 1,475 mathematical articles in his lifetime, mostly with co-authors. He strongly believed in and practised mathematics as a social activity, having 511 different collaborators in his lifetime (source).

Having no home, while globe trotting the world from place to place, living mostly for short periods in friend’s and colleagues houses, almost as if he was travelling from one set of mathematics, to another, it was not only the quantity of his work which was tremendous, but mainly the quality and impact of his works. It was not rare, that a single paper, produced a entire brand new field of research. One of my favourite examples, it’s his paper with *Rényi *on random graphs (image caption above): *Erdös*, P.; *Rényi*, A. (1960). “*On The Evolution of Random Graphs*“. *Magyar Tud. Akad. Mat. Kutató Int. Közl.* **5**: 17 [PDF]. Alone, this single 5 pages paper emerged a new science branch, critical in our times: *Complex Networks*. The work is now being cited +2500 times.

Fig. – *Erdös *and *Rényi *(1959, 1960, 1961) were the first to introduce the concept of random graphs in 1959. The simple model of a network involves taking some number of vertices, *N* and connecting nodes by selecting edges from the *N*(*N*-1)/2 possible edges at random (*Albert *and *Barabási *2002; *Newman *2003). Figure shows three random graphs where the probability of an edge being selected is *p*=0, *p*=0.1 and *p*=0.2. (a) Initially 20 nodes are isolated. (b) Pairs of nodes are connected with a probability of *p* of selecting an edge. In this case (b) *p*=0.1 , (c) *p*=0.2, notice how the nodes become quickly connected. The Erdös and Rényi random graph studies explore how the expected topology of the random graph changes as a function of the number of links. It has been shown that when the number of links is below 1/*N*, the graph is fragmented into small isolated clusters. Above this threshold the network becomes connected as one single cluster or giant component. We now know, that at the threshold the behaviour is indeterminate (*Strogatz *2001). Random graphs also show the emergence of subgraphs (below). *Erdös *and *Rényi *explored the emergence of these structures, which form patterns such as trees, cycles and loops. Like the giant component, these subgraphs have distinct thresholds where they forming different patterns (below).

Fig. – Different subgraphs appear at varying threshold probabilities in a random graph (*Albert *and *Barabási *2002)

## Recent Comments