Fixing our own Erdős discrepancy

 By permission of Fan Chung Graham,  artist.

Paul Erdős—Erdős Pál in Hungarian—would have been 100 this past Tuesday. He was a force of nature, a world stimulant. He popularized his colleague Alfred Rényi’s dictum that “a mathematician is a machine for turning coffee into theorems,” while supplying much of the perpetual motion for the world’s theorem-proving machines himself. His Wikipedia page lists his affiliations after leaving Notre Dame in 1952 as “itinerant,” though he was a regular visitor to several institutions around the world. Although known for long travels, he also experienced the shortest possible transit, from Memphis State University to the University of Memphis in 1994. His frequent collaborator Joel Spencer cited words delivered by Ernst Straus to honor Erdős’ 70th birthday, in 1983:

Just as the “special” problems that [Leonhard] Euler solved pointed the way to analytic and algebraic number theory, topology, combinatorics, function spaces, etc., so the methods and results of Erdős’ work already let us see the outline of great new disciplines, such as combinatorial and probabilistic number theory, combinatorial geometry, probabilistic and transfinite combinatorics and graph theory, as well as many more yet to arise from his ideas.

Today Dick and I would like to join others observing this important anniversary.

Actually we almost missed it—it was just by coincidence that Monday’s post was on one of Erdős’ most cherished problems, which he called “one of my oldest conjectures” in an article on open problems for the inaugural 1981 issue of the journal Combinatorica. That post itself was delayed more than a day by one of several kinds of events on the singular boundary between personal and professional that have punctuated my (our) calendar year 2013. I was scrolling through Facebook for news of another such event just before a noontime class on Tuesday when I saw a friend’s link to a lovely illustrated feature on the New York Times “Wordplay” blog. Then I checked Lance Fortnow’s post to see if its being the anniversary was really true.

Erdős is of course known for “Erdős Numbers,” meaning distances from him in the graph whose edges link co-authors on a recognized (mathematical) publication. The American Mathematical Society maintains an engine for computing them, at least in the graph restricted to entries in Mathematical Reviews. Dick and I both have Erdős Numbers of 2.

## My Meeting With Erdős

I met Erdős only once, exactly thirty years ago while I was a graduate student at Oxford University. I stayed one day in Cambridge with a friend before taking the ferry to Europe, and was allowed in to a late afternoon indoor reception of the 70th birthday conference organized by Béla Bollobás. My advisor Dominic Welsh was with Bollobás and Peter Cameron and (if I recall) Peter Neumann, and as I approached them he gave me a hand beckon to meet Erdős. My introducer mentioned my being a chess master, and that quickly led to my being posed a pointed question, for which I happened to have an answer.

Writing this post has actually finally spurred me to seek verification through appropriate channels for the answer I gave. My information came in 1976 from a relevant party in a brief phone call, of the pinch-myself-did-it-really-happen? kind. The gist was that something had happened to Bobby Fischer some months before the scheduled match he ultimately forfeited to Anatoly Karpov in 1975, and that the United States Chess Federation had gone along with his controversial pre-match demands partly in hope to buy time for him to recover. Through 1983 I had as-requested kept this belief to myself, but when the first words to me from the great man hit the nail on the head, I felt bound to make an exception. After a couple of sentences rounding off the conversation he’d been having with Bollobás and the others, Erdős inched me aside to a window, and said pretty much this:

Chess player, tell me… Why did Bobby Fischer not defend his title against Anatoly Karpov? I hear many things that people tell me, but none of them make any sense.

So I told him what I believed. He listened wordlessly, and then proclaimed with a finger wag,

That… makes sense!

I believe I also told Ronald Graham and Fan Chung during the harbor cruise for STOC 1990 in Baltimore, when the subject arose in a way that made me guess my words had been passed on. If my story brought Fischer relief from opprobrium in certain intellectual circles, for failing to play the match, I’ll be happy.

Erdős referred to people who stopped doing mathematics as having “died.” He must have wondered why the man at the top of a related intellectual field had taken himself out, while Erdős himself knew he would keep working until he died “in action”—as happened during a conference in Warsaw in 1996. Perhaps the thought that something had happened to make Fischer abdicate reduced the dissonance Erdős felt from it. Or maybe he was just being a chess fan.

## Another Story

My first doctoral student, Arun Jagota, came over to me in 1991–92 from a colleague, under whom he had been researching neural networks of the kind named for John Hopfield. He had formulated a notion of an “almost-clique” in a graph, and asked me if it were known. I didn’t know it, and did not see a way to trivialize it or otherwise “deconstruct” it, but I felt it needed further context before it could go in a submitted paper. I basically said there were two things one could do:

1. Go on a trove of the literature—I specifically mentioned the Journal of Combinatorial Theory, Series B—to find either it or what’s close to it; or

2. Reach and ask someone who knows everything—someone like Paul Erdős.

OK, I may not have specifically said Erdős, but I definitely drew from the category of people outside my own e-mail contacts, and whom else would I have named? Being a hard worker, Arun chose option 1. and spent a lot of time amid the library stacks of the journal. A couple months later he came back showing what he had found, which I could tell was no overlap, so I greenlighted it for a paper and chapter of his thesis, which he defended in 1993.

Arun earned a postdoc at what was then Memphis State and shortly became the University of Memphis, which afforded him the opportunity to try strategy 2. Evidently it succeeded, for Arun’s idea was integral to the paper, “Large subgraphs of minimal density or degree,” also with Ralph Faudree and Tomasz Łuczak, published in the Journal of Combinatorial Mathematics and Combinatorial Computing, 22: 87–96, 1996.

According to the title of Spencer’s AMS Notices article I should have addressed Erdős as “Uncle Paul,” but oddly in mathematical genealogy terms the relationship came out reversed.

## Numbers and Prizes

The Collaboration Graph is an important example of a social network, and there have been studies of its structure. An overview is maintained by the Erdős Number Project at Oakland University. Among oddities documented on this page is the fact that Erdős’ collaborators—those with Erdős number 1—have zero overlap with the winners of the Fields Medal and several other major prizes. Erdős himself populated the Wolf Prize, and Endre Szemerédi last year became the first such winner of the Abel Prize. That page does not mention the ACM Turing Award, but it appears that the closest we come to overlap is via Frances and Andy Yao.

We take this time to congratulate Shafi Goldwasser and Silvio Micali for winning the 2012 ACM Turing Award, for their many contributions to provable security and interactive proof systems. We also congratulate Shafi for being included in a feature that CNN ran earlier this month to mark International Women’s Day.

We also note several responses to the last post with research ideas on the Erdős Discrepancy Problem, including this by Sasho Nikolov, these by Gil Kalai, and this by Jeffrey Shallit, who has Erdős number 1. Gil has a photo of Erdős also including Łuczak, while some other stories of “Uncle Paul” are by Cameron here and the Grahams here.

## Open Problems

Here’s possibly the simplest Erdős Prize Problem to state: if ${\sum_n 1/x_n}$ diverges, must the integer sequence ${[x_n]}$ have arbitrarily long arithmetic progressions?

March 29, 2013 8:45 am

What is this number supposed to measure? Just because a mathematician has been particularly prolific, this doesn’t make them the center of the mathematical universe… You could take any famous actor and define their number recursively: if you’ve played in a movie with them, then your number is one. If you’ve played in a movie with someone who’s played with them, then your number is two, and so on… Even in Hollywood they haven’t been thinking yet of defining such a silly measure of popularity. So I don’t know what the Erdös number tells, but its very existence is quite telling about the mathematical community.

March 30, 2013 1:29 am

This is just another way of saying– most people live in their own world.

March 29, 2013 11:02 am

Wahoo! I’m impressed! When they say great ideas have to be discovered several times independently…
But you’ll notice that this time, it was the mathematicians who inspired the show business. 🙂

March 29, 2013 4:13 pm

I understand from your text that you may still not be at liberty to say (which would be unfortunate), but it’s hard not to ask:

What happened to Fischer?

• March 29, 2013 4:45 pm

I am less sure of it than the caller was, and also less sure now than I was in 1983 because it has not appeared in recent books etc. on Fischer. This is what I am hoping to verify, or at least get a read on.

March 30, 2013 9:31 am

Is this such an embarassing event that neither Karpov nor the FIDE would be notified of it?

3. March 29, 2013 4:51 pm

erdos, a mathematical einstein figure from the 20th century. one of the greats. brilliant, and yet he was very careful and lived out that expression “choose your battles wisely”. see also erdos100, tribute to a brilliant contrarian with lots of links

April 1, 2013 8:02 am

Interesting article. Yes, he was an impressive thinker – if not exactly in the same style as Einstein. I think he was quite lucky to work before the Internet era, for it gave him the opportunity to meet many people in real life and to keep his brain active. It was the Swiss physicist Auguste Piccard who used to say that “exploration is the sport of the scientist.” 🙂

4. March 30, 2013 12:43 am

The Combinatorica article (1981) link seems to break for me.

• March 30, 2013 8:10 am

Ah, it broke even on my machine with a Springer sub. I have found and used instead the Renyi site’s free link to all of his papers up to 1989: http://www.renyi.hu/~p_erdos/Erdos.html.

March 30, 2013 10:14 am

Erdos is obviously an important mathematician, but I think his model of work is actually harmful, to a certain extent at least, to TCS (and maybe even combinatorics).
My impression is that his style, concentrating solely on concrete problem solving, serves as a limiting model to many researchers in TCS. Glorifying problem solving on the expense of theory building and pursuing long term directions to solve fundamental open questions does not seem to be the right balance in research.
Of course, everyone has his or hers own style of research, but I feel that celebrating mainly figures like Erdos in TCS is wrong.
This relates to Gower’s paper “Two Cultures of Mathematics” in which he argues for the legitimacy/importance of the Erdos’ style mathematics. It seems that in TCS we have to argue for the opposite now to gain the optimal balance.

March 30, 2013 2:40 pm

Indeed, this is especially true of a field such as TCS – full of open problems and where the right objects of study seem to be missing.

April 1, 2013 4:02 am

It seems to me that the objects are clearly defined and studied in combinatorial optimization. It’s just that the theory is not powerful enough as it stands… and possibly never will be.