Skip to content

Fun Fact: The Erdős Number

Abstract

Paul Erdős published roughly 1,400 papers with 514 different coauthors, more than any mathematician before him, and mostly while living out of a suitcase. His colleagues turned that into a joke with a definition: Erdős has Erdős number 0, anyone who published with him has 1, anyone who published with them has 2, and so on. It is a shortest-path computation on a collaboration graph, which is exactly the kind of object Erdős spent his life studying. Bill Gates has an Erdős number of 4, through the one research paper he wrote before Microsoft ate his time.

The Number

The Erdős Number Project, run by the mathematician Jerry Grossman, has computed the numbers from the Mathematical Reviews database since the 1990s. Its lists, in the version of August 2025 and complete through mid-2025, name 514 people with Erdős number 1 and 13,782 with Erdős number 2: 14,297 people within two hops.

The wider census is older, because the project lost its access to the Mathematical Reviews data. On the July 2004 snapshot, 1,416 Erdős papers were covered by Mathematical Reviews, roughly 268,000 published mathematicians had a finite Erdős number, their mean was 4.65 and their median 5, and the largest finite number anyone held was 13, which five people managed. Another 84,000 published authors had never written a joint paper with anybody, so their number was infinite by default.

Gates, Number 4

In 1979 a Harvard undergraduate named William H. Gates wrote a paper with Christos Papadimitriou called “Bounds for Sorting by Prefix Reversal”, in Discrete Mathematics. The problem is the pancake problem: a stack of pancakes of different sizes must be sorted by repeatedly sliding a spatula under some prefix of the stack and flipping it. Gates and Papadimitriou proved the number of flips needed is at most (5n+5)/3 and at least 17n/16 for n divisible by 16. The upper bound stood for thirty years.

That single paper connects him to the graph: Gates published with Papadimitriou, who published with Xiaotie Deng, who published with Pavol Hell, who published with Erdős. Four steps, and the project is careful to say “at most 4”, since a shorter path nobody has spotted would still count.

The chain is short because computer science and combinatorics were the same people for a while. Anyone who worked on graph algorithms, random structures or combinatorial optimisation in the 1970s and 1980s was one or two hops from Erdős without trying.

Still Growing

Erdős died in 1996. His coauthor count did not stop, because unfinished joint work keeps appearing: the project’s five-yearly update, covering MathSciNet and DBLP through mid-2025, added two new people with Erdős number 1 and about 1,200 with Erdős number 2. The graph gains vertices around a fixed centre almost thirty years after the centre stopped travelling.

The joke has extensions. The Erdős-Bacon number adds the Hollywood collaboration graph, where Kevin Bacon plays the same role that Erdős does in mathematics, and the small population who have both an academic publication record and a film credit can compute a sum. Natalie Portman, who published a neuroscience paper as Natalie Hershlag, is the usual example.

📚 Sources