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)