Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!news-out.cwix.com!newsfeed.cwix.com!torn!watserv3.uwaterloo.ca!undergrad.math.uwaterloo.ca!neumann.uwaterloo.ca!alopez-o
From: [email protected] (Alex Lopez-Ortiz)
Newsgroups: sci.math,news.answers,sci.answers
Subject: sci.math FAQ: Erdos Number
Followup-To: sci.math
Date: 17 Feb 2000 22:52:00 GMT
Organization: University of Waterloo
Lines: 100
Approved: [email protected]
Expires: Sun, 1 Mar 1998 09:55:55
Message-ID: <[email protected]>
Reply-To: [email protected]
NNTP-Posting-Host: daisy.uwaterloo.ca
Summary: Part 12 of 31, New version
Originator: [email protected]
Originator: [email protected]
Xref: senator-bedfellow.mit.edu sci.math:347392 news.answers:177512 sci.answers:11220

Archive-name: sci-math-faq/erdosnumber
Last-modified: February 20, 1998
Version: 7.5

                               Erdos 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
  Erdos number of X is the length of the shortest path in this graph
  connecting X with Erdos.

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

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

  Why people care about it?

  Nobody seems to have a reasonable answer...

  Who is Paul Erdos?

  Paul Erdos was an Hungarian mathematician. He obtained his PhD from
  the University of Manchester and spent most of his efforts tackling
  "small" problems and conjectures related to graph theory,
  combinatorics, geometry and number theory.

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

  Paul Erdvs died on September 20, 1996.

  At this time the number of people with Erdos 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/erdos or on the Web
  at http://www.acs.oakland.edu/ grossman/erdoshp.html. At this time it
  contains a list of all co-authors of Erdos and their co-authors.

  On this topic, he writes

    Let E_1 be the subgraph of the collaboration graph induced by
    people with Erdos 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 Erdos. 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 Erdos 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 Erdos 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 Erdos number 2 have only one
    co-author with Erdos number 1 (i.e., each such person has a unique
    path of length 2 to p). However, their mean number of Erdos 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, Erdos 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 Erdos component, with
    Erdos number at most 9. Since this group includes people working in
    theoretical physics, one can conjecture that most physicists are
    also in the Erdos 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 Erdos
    component, and what is the order of the second largest component?

     References

  Caspar Goffman. And what is your Erdos 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].
    _________________________________________________________________

--
Alex Lopez-Ortiz                                         [email protected]
http://www.cs.unb.ca/~alopez-o                       Assistant Professor
Faculty of Computer Science                  University of New Brunswick