Thursday, September 03, 2009

Six degrees of Paul Erdős



Around the lunch table at any mathematics department, a certain topic of conversation is bound to arise eventually.

"I bet yours is pretty low," says A to B, who is older.

"Oh no," protests B. "High. Mine's at least a five."

"Anybody have a four?" A says, looking around the table slyly. C raises a hand tentatively. But before C can explain, A says, "Well, I'm a three." C lowers the hand; A looks quite pleased.

Then D approaches the group, leaning heavily on a cane. D's eyes twinkle behind thick, tortoiseshell glasses. "What's this all about, then?"

Now A is visibly nervous. "Oh, nothing, D. Just—"

"We were just hearing about how A is a three," C says quickly, shooting A a triumphant glance.

"Two!" exclaims D, making a show of looking astounded. "Quite good, A. Quite good. Bravo."

"What about you, D," says B. "What's yours?"

"Well, I feel very blessed," D says. "He was an old friend of mine, in fact. And we did of course collaborate." D sighs heavily. "So I must fess up - I'm a one."

If you're a mathematician or physicist, you might have found yourself having this conversation with colleagues at some point in your career. If not, you're probably wondering what on earth I'm talking about. I was certainly confused when the topic came up over lunch today; I was in the company of a mathematician, an engineer, and two physicists. It's math's equivalent of the classic game, "six degrees of Kevin Bacon"—how many collaborations are you away from the mathematician Paul Erdős?

Mathematicians, because they love tracking this sort of thing, have created a kind of math out of it, called an Erdős number. Here's how it works - Paul Erdős's Erdős number is zero. Those who have written a paper with him have an Erdős number of one; those who write a paper with someone with an Erdős number one, but who haven't collaborated with Erdős directly, have an Erdős number of two. Hence the characters in this brilliant strip from xkcd, standing in line to get their names on a paper with the resurrected Erdős so they can all have Erdős numbers of one. In the way the Erdős math is defined, most of us non-mathematicians have an Erdős number of infinity, which denotes no possible trail of co-author connections links back from us to the man himself.

Why Erdős, you ask? Why not someone more famous, like Einstein or Feynman or Poincare? The reason is the same as why Kevin Bacon is the universal connector for movie stars—he's worked with everybody. Erdős, who died in 1996 at the age of 83, was the most prolific mathematician in history. He boasts 1525 published papers (and counting, with posthumous publications) and 511 collaborations; 8674 people can lay claim to having an Erdős number of at most two. Just like most actors and directors are within 6 hops of Kevin Bacon, writes Mike Hoffman, a math professor at the US Naval Academy, "hardly any [USNA faculty] who have written joint papers have an Erdős number greater than 5." One would expect most mathematicians at other to have a finite—and small—Erdős number as well.



The Erdős Number Project, run by math professor Jerry Grossman at Oakland University in Michigan, is a universe all its own based on this tangled web of collaborations. Grossman has run stats on the Erdős network and on the larger network of all mathematicians. Turns out for mathematicians, it's not quite six degrees:

The appropriate phrase for C, then, is perhaps "eight degrees of separation", if we wish to account for three quarters of all pairs of mathematicians.
In terms of the stats on the set of mathematicians who can be linked back to Erdős, USNA's Mike Hoffman's comment makes sense:

Erdös number 0 --- 1 person
Erdös number 1 --- 504 people
Erdös number 2 --- 6593 people
Erdös number 3 --- 33605 people
Erdös number 4 --- 83642 people
Erdös number 5 --- 87760 people
Erdös number 6 --- 40014 people
Erdös number 7 --- 11591 people
Erdös number 8 --- 3146 people
Erdös number 9 --- 819 people
Erdös number 10 --- 244 people
Erdös number 11 --- 68 people
Erdös number 12 --- 23 people
Erdös number 13 --- 5 people

Thus the median Erdös number is 5; the mean is 4.65, and the standard deviation is 1.21.


Some famous names have low Erdős numbers— Bill Gates has an Erdős number of 4, Steven Chu's is 7, and Albert Einstein is 2. But as we can see from the data above, the really rare thing is actually having a high Erdős number, while still being connected to him.



You might expect that someone who wrote so many papers and worked with so many people would be a strange character. You're right. "His peculiarities are so numerous it is impossible to describe them all," wrote fellow mathematician Stanislaw Ulam in 1976. Born in 1916 in Hungary (hence the crazy not-quite-umlaut over the o in his name), Erdős lived a life of "mathematical pilgrimage," as one colleague termed it. Free from the burdens of a wife, children, credit card, or house, he traveled from collaboration to collaboration, criss-crossing the globe to pursue the next great problem. He would show up at a colleague's doorstep with his suitcases and, with the words, "My mind is open!" would announce his stay; legend has it that banging pots and pans was his way of announcing it was time to get up and work.



For more information on this delightfully kooky human being, the Erdős Number Project has an exhaustive list of resources.

Wondering what your Erdos number is? Check out this handy search function from the American Mathematical Society's MathSciNet site. I for one, am wondering: who would be the Paul Erdős of the physics world?

2 comments:

  1. I wonder if mathematics or physics has more famous quirky people?

    Erdos, Einstein, Feynman, Von Neumann, Turing, Gauss, the list goes on and on...

    ReplyDelete
  2. can somebody plz explain it to me easier as i am in college and need this for my homework i am only in year 7 as well!!!!!

    ReplyDelete