You are here

The Mathematics of Paul Erdős II

Ronald L. Graham, Jaroslav Nešetřil, and Steve Butler, editors
Publication Date: 
Number of Pages: 
[Reviewed by
Craig P. Bauer
, on

For the last 100 years, physics has had living icons to represent the subject to the masses: Albert Einstein, Richard Feynman, Stephen Hawking, and others. All of these physicists are well represented on the shelves of every bookstore. There are popular accounts of their lives, as well as films and more technical explanations of their contributions. Every scientist is familiar with these names, and much of the general public has heard of at least two of the three.

By comparison, mathematics has had a PR problem for the last 100 years. The average American cannot name any living mathematicians. Even for undergraduate math and science majors the situation is often not much better. For example, I asked students in my Discrete Math class to name a living mathematician, not counting professors they’ve had. Nobody could do it! You may be surprised at how poor the results are if you ask your own students. I suggest making it an extra credit question on a test to get full participation. They all know past greats like Pythagoras and Newton, but they don’t know who the present greats are. On the local level (i.e. in our classrooms), we can remedy the situation by occasionally including tales of current mathematics, being sure to include names, alongside the old results we must convey.

But what is the global answer? Who can we put before the whole world as the public face of mathematics? Certainly popularizers like Martin Gardner have done mathematics a great service, but they are not in the same league as the aforementioned physicists or the big names of today. People such as Terence Tao, who do belong in that league, seem to be known exclusively to other mathematicians. Even if we look to the past, there are not many well-known figures. Alan Turing has, of course, been the focus of much attention in recent decades, but he was not known to general audiences during his life. Fractals have experienced tremendous mainstream appeal, but Benoit Mandelbrot did not become a household name and no book length biography of Mandelbrot saw print until his excellent autobiography was posthumously released. John Nash has attracted the public’s interest, but his mathematics was not the focus of much of it. Perhaps the closest to the proposed icon we’ve come in the last 100 years seems to be Paul Erdős. Others have captured the public’s attention briefly (Andrew Wiles, Grigori Perelman, etc.), but Erdős was celebrated in a film and two biographies aimed at a wide audience.

For those not already familiar with these items, the citations are

·         George Paul Csicsery, N is a Number, a Portrait of Paul Erdős, 57-min. documentary film, Zala Films, 1993

·         Paul Hoffman, The Man Who Loved Only Numbers, Hyperion (New York, 1998).

·         Bruce Schecter, My Brain Is Open, Simon & Schuster (New York, 1998).

Sadly, the books only appeared after Erdős’s death.

The biographies will satisfy those looking for the basic story of Erdős’s life and cute anecdotes about his eccentricities. As a bonus, they give a sense of the culture of mathematics. Although I recommend them, these works aimed at wide audiences cannot delve deeply into Erdős’s mathematics. The volumes under discussion in this review do. Experts from around the world have contributed papers that survey and/or expand upon Erdős’s mathematical work. By necessity, most of the papers are written at a high level.

After about fifty pages of background and introductory material, the reader is treated to the paper “Some of My Favorite Problems and Results” by “P. Erdős (Deceased).” At first I thought the “(Deceased)” part was a nod to Erdős’s placing a growing list of initials after his name as he gradually approached that state. At the age of 75 his signature was followed by PGOMLDADLDCD, which stood for “Poor Great Old Man, Living Dead, Archaeological Discovery, Legally Dead, Counts as Dead.” However, the indication of his demise was not apparently meant to be tongue-in-cheek, as the authors of the next four papers were given the same identification. These papers constitute first part of the book, which is titled “Early Days.” We should not be surprised that there are few who still remember these days, but it is good that they went on record for the first edition of this work, which came out in 1996. The present edition was released in 2013 to coincide with what would have been Erdős’s hundredth birthday. I have not done a comparison of the first edition with the update, but I did find that several papers have additions indicating the great progress that has been made between editions in fields Erdős helped create.

One intriguing paper from the “Early Days” section is by Cedric A. B. Smith and titled “Did Erdős save Western Civilization?” This paper details how one of Erdős’s conjectures had a butterfly-like effect and ended up leading William T. Tutte from chemistry to math, and on to Bletchley Park, where some of England’s greatest minds worked on breaking Nazi codes and ciphers. Smith then vaguely refers to a Nazi cipher machine (the reader will likely be thinking of Enigma) and writes (p. 90): “Very plausible rumor says that Tutte supplied the vital clue, possible avoiding military defeat. The consequence of a Nazi victory would have been horrific – civilization was saved. And it all began with a conjecture by Erdős!” Tutte did carry out very important work, but it was on the less well-known Lorenz cipher machine used by the Nazis, not Enigma.

Volume I continues with Number Theory, Randomness and Applications, and Geometry. Volume II has Combinatorics and Graph Theory, Ramsey and Extremal Theory, and Infinity. To wrap things up, a statistical analysis of Erdős’s publications, with an emphasis on his collaborations is provided, followed by a list of 1,525 papers by Erdős and his 511 coauthors. The papers are in English, Hungarian, German, French, Russian, and Norwegian.

To describe the contents of these volumes a little better, let me define a paper to be “readable” if it can be understood without having to consult any outside sources. That is, any terms that the reader would need defined, are in fact defined in the paper itself. Clearly papers that are not self-contained in this way can still be read (and fully understood, if background reading is done first), but that is not how I am defining the term readable here. I also note that what’s readable to one individual may not be readable for another. Since I am writing for MAA Reviews, I presume most readers are MAA members, and as such perhaps devote more time to their classes than research. With these qualifications, I estimate about 60% of the two volumes to be readable. Again, this is for the typical teaching professor. For people who devote more time to research than classes, I expect a far higher percentage of the material would be accessible, but then they would also already know a higher percentage of it. At least one contributor considered the problem, for in the wrap-up of his paper (vol II, p. 296), he wrote “How could I explain on 30 or 50 pages the influence of Erdős on Extremal Graph Theory to people who don’t know it. And why should I explain to those who know it.” One very difficult paper in the Infinity section of volume II offers a one-word proof of a theorem with six parts. (Vol II, p. 448. The word is “Straight.” On page 472 of the same paper a proof is provided by the word “Think.”)

Unable to digest everything, I still felt like I got a much better understanding of Erdős’s work from these volumes (and also of how this work influenced others up to the present day). I recommend them to any mathematician who seeks such an understanding. If, on the other hand, what is sought is neat material to weave into undergraduate courses, you are asking for something the volumes did not set out to supply. Having said his, there is at least one item I’ll be making use of next semester.

Let \(A_1, \dots, A_m\) be \(n\)-sets in an arbitrary universe \(\Omega\). The family \( \mathcal{A} =\{\mathcal{A}_1, \dots, \mathcal{A}_m\}\) is 2-colorable (Erdős used the term “Property B”) if there is a 2-coloring of the underlying points \(\Omega\) so that no set \(A_i\) is monochromatic. In 1963 Erdős gave perhaps the quickest demonstration of the Probabilistic Method.

Theorem 4 ([5]). If \(m<2^{n-1}\) then \(A\) is 2-colorable.

Proof. Color \(\Omega\) randomly. Each \(A_i\) has probability \(2^{1-n}\) of being monochromatic, the probability some \(A_i\) is monochromatic is then at most \(m2^{1-n} < 1\) so with positive probability no \(A_i\) is monochromatic. Take that coloring. □

(Vol. I, p. 442. The [5] is the original author’s reference to Erdős’s paper.)

Those seeking a higher percentage of possible classroom material, while keeping an Erdős connection can turn to Proofs from THE BOOK by Martin Aigner, Günter M. Ziegler and Karl H. Hofmann, Springer 2009. The first edition of this book appeared in 1998. The title arises from a book (which Erdős claimed God has) that contains every theorem and the best proof of each. One of Erdős’s highest compliments was “That’s a proof from THE BOOK.” It should be understood that Erdős was actually an atheist. Nevertheless he referred to God as the supreme fascist, or SF for short. Supreme because he had THE BOOK, and a fascist because he didn’t let you look at it until you died.

Although a complete survey of publications covering Erdős and his work is beyond the scope of this review, I am including one final item that saw print in June 2013. It is for the epsilons, and I introduce it below by quoting a non-mathematician reviewer: “The Boy Who Loved Math: The Improbable Life of Paul Erdős, by Deborah Heiligman, illustrated by LeUyen Pham. Talk about unique. If you thought the biography of an eccentric Hungarian-born mathematician couldn't be turned into a children's book, think again, my friend.” (Lauren Daley's Book Lovers: Best books to buy for kids, December 14, 2013 12:00 AM )

Craig Bauer is the author of Secret History: The Story of Cryptology. He teaches at York College of Pennsylvania.

Part I Combinatorics and Graph Theory


Reconstruction Problems for Digraphs

Neighborly Families of Boxes and Bipartite Coverings

On the Isolation of a Common Secret

Properties of Graded Posets Preserved by Some Operations

The Dimension of Random Graph Orders

Hereditary and Monotone Properties of Graphs

Cycles and Paths in Triangle-Free Graphs

Problems in Graph Theory from Memphis

Some Remarks on the Cycle Plus Triangles Problem

Intersection Representations of the Complete Bipartite Graph

Reflections on a Problem of Erdős and Hajnal

The Chromatic Number of the Two-Packing of a Forest

Part II Ramsey and Extremal Theory


Ramsey Theory in the Work of Paul Erdős

Memories on Shadows and Shadows of Memories

A Bound of the Cardinality of Families Not Containing Δ-Systems

Flag Algebras: An Interim Report

Arrangeability and Clique Subdivisions

A Finite Partition Theorem with Double Exponential Bound

Paul Erdős' Influence on Extremal Graph Theory

Applications of the Probabilistic Method to Partially Ordered Sets

Part III Infinity


A Few Remarks on a Conjecture of Erdős on the Infinite Version of Menger's Theorem

The Random Graph

Paul Erdős' Set Theory

Set Theory: Geometric and Real

On Order-Perfect Lattices

The PCF Theorem Revisited

Paul Erdős: The Master of Collaboration

List of Publications of Paul Erdős