What is an Erdös Number ?

Paul Erdös, the late widely-traveled and incredibly prolific Hungarian mathematician of the highest caliber, wrote hundreds of mathematical research papers in many different areas, many in collaboration with others. His Erdös number is 0. His co-authors have Erdös number 1. People other than Erdös who have written a joint paper with someone with Erdös number 1 but not with Erdös have Erdös number 2, and so on. If there is no chain of co-authorships connecting someone with Erdös, then that person's Erdös number is said to be infinite.

In graph-theoretic terms, the collaboration graph C has all authors as its vertices; the vertex p is Paul Erdös. There is an edge between u and v if u and v have published at least one article together. (We will adopt the most liberal interpretation here, and allow any number of other co-authors to be involved; for example, a six-author paper is responsible for 15 edges in this graph, one for each pair of authors. Other approaches would include using hypergraphs or multigraphs or multihypergraphs.)

The Erdös number of v, then, is the distance (of the shortest path) in C from v to p. The set of all authors with a finite Erdös number is called the Erdös component of C. It has been conjectured that the Erdös component contains almost all present-day publishing mathematicians (and has a not very large diameter), but perhaps not some famous names from the past, such as Gauss. Clearly, any two people with a finite Erdös number can be connected by a string of co-authorships, of length at most the sum of their Erdös numbers.

My Erdös Number is 4

• Paul Erdös
• Daniel J. Kleitman
• Michael L. Fredman
• Bruce W. Weide
• Scott M. Pike

Path Edge	Publication
Erdös  →  Kleitman	Boris Aronov, Paul Erdös, Wayne Goddard, Daniel J. Kleitman, Michael Klugerman, János Pach, Leonard J. Schulman. Crossing Families. 7th Annual Symposium on Computational Geometry, pp. 351-356 (1991).
Kleitman  →  Fredman	Walter A. Burkhard, Michael L. Fredman, Daniel J. Kleitman.Inherent Complexity Trade-Offs for Range Query Problems. Theoretical Computer Science 16(3): 279-290 (1981).
Fredman  →  Weide	Michael L. Fredman, Bruce W. Weide. On the Complexity of Computing the Measure of U[ai, bi], CACM 21(7): 540-544 (1978).
Weide  →  Pike	Nigamanth Sridhar, Scott M. Pike, Bruce W. Weide. Dynamic Module Replacement in Distributed Protocols., ICDCS 2003, pp. 620-627, IEEE Press, 2003.

Epilogue

The article Why the modern world needs caffeine by Malcolm Gladwell [The New Yorker: 30 July 2001] references the following anectdote from the book The Man Who Loved Only Numbers by Paul Hoffman.

Paul Erdös "put in nineteen-hour days, keeping himself fortified with 10 to 20 milligrams of Benzedrine or Ritalin, strong espresso and caffeine tablets. ‘A mathematician,’ Erdös was fond on saying, ‘is a machine for turning coffee into theorems.’" Once, a friend bet Erdös $500 that he could not quit amphetamines for a month. Erdös took the bet and won, but, during his time of abstinence, he found himself incapable of doing any serious work. "You've set mathematics back a month," he told his friend when he collected, and immediately returned to his pills.