Fixing our own Erdős discrepancy

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 diverges, must the integer sequence have arbitrarily long arithmetic progressions?