Erdös Number

Form an undirected graph where the vertices are academics, and an edge connects academic X to academic Y if X has written a paper with Y. The Erdös number of X is the length of the shortest path in this graph connecting X with Erdös.

Erdös has Erdös number 0. Co-authors of Erdös have Erdös number 1. Einstein has Erdös number 2, since he wrote a paper with Ernst Straus, and Straus wrote many papers with Erdös.

The Extended Erdös Number applies to co-authors of Erdös. For People who have authored more than one paper with Erdös, their Erdös number is defined to be 1/# papers-co-authored.

Why people care about it?

Nobody seems to have a reasonable answer...

Who was Paul Erdös?

Paul Erdös (died on September 20, 1996) an Hungarian mathematician was one of the most important mathematicians of the 20th century. He obtained his PhD from the University of Manchester and had worked in dozens of fields such as problems and conjectures related to graph theory, combinatorics, geometry and number theory, and written over 1,200 mathematical papers. He was renowned for his ability to identify new problems in math and new directions math should take. It was his custom to offer prizes for the solutions to problems he posed.

He is one of the most prolific publishers of papers; and is also and indefatigable traveller.

At this time the number of people with Erdös number 2 or less is estimated to be over 4750, according to Professor Jerrold W. Grossman archives. These archives can be consulted via anonymous ftp at vela.acs.oakland.edu under the directory pub/math/ Erdös. At this time it contains a list of all co-authors of Erdös and their co-authors.

On this topic, he writes

Let E_1 be the subgraph of the collaboration graph induced by people with Erdös number 1. We found that E_1 has 451 vertices and 1145 edges. Furthermore, these collaborators tended to collaborate a lot, especially among themselves. They have an average of 19 other collaborators (standard deviation 21), and only seven of them collaborated with no one except Erdös. Four of them have over 100 co-authors. If we restrict our attention just to E_1, we still find a lot of joint work. Only 41 of these 451 people have collaborated with no other persons with Erdös number 1 (i.e., there are 41 isolated vertices in E_1), and E_1 has four components with two vertices each. The remaining 402 vertices in E_1 induce a connected subgraph. The average vertex degree in E_1 is 5, with a standard deviation of 6; and there are four vertices with degrees of 30 or higher. The largest clique in E_1 has seven vertices, but it should be noted that six of these people and Erdös have a joint seven-author paper. In addition, there are seven maximal 6-cliques, and 61 maximal 5-cliques. In all, 29 vertices in E_1 are involved in cliques of order 5 or larger. Finally, we computed that the diameter of E_1 is 11 and its radius is 6.

Three quarters of the people with Erdös number 2 have only one co-author with Erdös number 1 (i.e., each such person has a unique path of length 2 to p). However, their mean number of Erdös number 1 co-authors is 1.5, with a standard deviation of 1.1, and the count ranges as high as 13.

Folklore has it that most active researchers have a finite, and fairly small, Erdös number. For supporting evidence, we verified that all the Fields and Nevanlinna prize winners during the past three cycles (1986-1994) are indeed in the Erdös component, with Erdös number at most 9. Since this group includes people working in theoretical physics, one can conjecture that most physicists are also in the Erdös component, as are, therefore, most scientists in general. The large number of applications of graph theory to the social sciences might also lead one to suspect that many researchers in other academic areas are included as well. We close with two open questions about C, restricted to mathematicians, that such musings suggest, with no hope that either will ever be answered satisfactorily: What is the diameter of the Erdös component, and what is the order of the second largest component?

References

Caspar Goffman. And what is your Erdös number? American Mathematical Monthly, v. 76 (1969), p. 791.

Tom Odda (alias for Ronald Graham) On Properties of a Well- Known Graph, or, What is Your Ramsey Number? Topics in Graph Theory (New York, 1977), pp. [166-172].

Why is there no Nobel in mathematics? Human Interest Fields Medal Math Links


alopez-o@daisy.uwaterloo.ca Sat Jan 6 22:47:26 EST 1996