Skip to Main Content

Complex Networks

Feature Column Archive

6. The Erdős graph

Paul Erdős was one of the most remarkable and colorful mathematicians of the 20th century.

A photo of Paul Erdos

He was born in Hungary and showed mathematical talent at an early age. Eventually he evolved a way of life where he had no "fixed home" but traveled around the world from one place to another where mathematics was being done, working on mathematical problems and inspiring others to do so. Erdős was a very prolific writer, producing many papers in conjunction with others that he inspired. His papers showed a great range of interest but were concentrated in the areas of number theory, combinatorics, graph theory, and discrete geometry. Erdős has often been associated with the observation that "a mathematician is a machine for converting coffee into theorems" but this "characterization" appears to be due to his friend, Alfred Rényi. This thought was developed further by Erdős' friend the Hungarian mathematician Paul Turán (1910-1976), who suggested that weak coffee was suitable "only for lemmas." Given Erdős' penchant for collaborative work and his own interest in the theory of graphs, it is natural to use graph theory to get insights into the way mathematicians collaborate using Erdős as an example, though perhaps a singular one.

Professor Jerrold Grossman (Oakland University) regularly updates and expands the insights into collaboration among mathematicians with the Erdős Number Project. The idea is to see how long a chain it takes to connect any given mathematician with a chain of collaborators to reach Erdős. Thus, if a person has written a research paper with a person, who wrote a research paper with Erdős, such a person has Erdős Number 2. Erdős himself has Erdős Number 0, while people who wrote a joint paper with Erdős have Erdős Number 1. The number of such individuals is currently known to be 509! Grossman and his collaborators have obtained an understanding into the way the mathematics community works together in developing new mathematics.

The mathematics of networks is drawing on many different parts of mathematics, statistics, probability, combinatorics, graph theory, analysis, and matrices, to get insights. No doubt more surprises are in store for us in addition to the many which have been recently discovered.

  1. Introduction
  2. Some history and a network primer
  3. Random networks
  4. Networks and epidemics
  5. Insights from probability and statistics
  6. The Erdős graph
  7. References