PDFLINK |
The Discrete Mathematical Charms of Paul Erdős: A Simple Introduction
Communicated by Notices Associate Editor Emily Olson
In The Discrete Mathematical Charms of Paul Erdős: A Simple Introduction, Vašek Chvátal tells the story of many discrete mathematical ideas, centered around the work of Paul Erdős. The book covers a wide range of topics in which Erdős left an indelible impression, including Ramsey theory, graph coloring, extremal graph and set theory, and discrete geometry. The foundation of this book is Chvátal’s lecture notes from a graduate-level discrete mathematics class he taught at Concordia University in the late 2000s, just over a decade after Erdős’ death. Chvátal does an exceptional job of putting the mathematical discoveries in their historical context and combining them with photos, personal anecdotes about his time spent with Erdős, and letters between the two. This context, along with the topics chosen and the clear writing, make this book exceptional.
The Mathematics
Early in each chapter the reader is presented with a definition, conjecture, or theorem introducing the topic. After a proof, Chvátal shows the development of the topic over time, including extensions, generalizations, and related results, many with proofs. There are no exercises in the book; the chapters end with stories and photos. The nearly 400 references in this book are comprehensive, allowing interested readers to delve deeper into any topic they choose.
As an example, the first chapter, entitled A glorious beginning: Bertrand’s postulate, begins with teenage Erdős’ brilliant elementary proof of Bertrand’s postulate that for every positive integer there is at least one prime number greater than , and at most Following this proof are sketches of earlier proofs of Bertrand’s postulate by Chebyshev, Landau, and Ramanujan. The chapter concludes with other results and open problems concerning prime numbers, with recent work on small gaps between consecutive primes and conjectures of Erdős on large gaps between consecutive primes and primes in arithmetic progressions. Chvátal provides a chronology of the results in each of these areas and even includes the amounts of money Erdős promised to those who proved his conjectures. .
The remaining ten chapters cover
- •
discrete geometry, including several proofs of the De Bruijn–Erdős Theorem;
- •
Ramsey numbers, ending with a proof of Ramsey’s Theorem in full generality;
- •
delta-systems, introduced by Erdős and Rado in 1960;
- •
extremal set theory, including Sperner’s Theorem and the Erdős–Ko–Rado Theorem;
- •
van der Waerden’s Theorem and van der Waerden numbers;
- •
extremal graph theory, beginning with Turán’s Theorem;
- •
the Friendship Theorem and strongly regular graphs;
- •
chromatic numbers, with a focus on graphs with large chromatic number;
- •
random graphs and finite probability theory; and
- •
Hamilton graphs, including a discussion of one of three joint papers Chvátal wrote with Erdős.
Chvátal writes that when teaching the class from which this book emerged, he generally covered nine of the eleven chapters over twelve 90-minute sessions. Given the breadth of topics and the depth of each chapter, the audience for this book should have at least the mathematical maturity of a beginning graduate student studying discrete mathematics.
Chvátal attempts to make the work accessible, perhaps to an advanced undergraduate audience, in two ways. First, he includes two appendices on prerequisite material. One is titled “A few tricks of the trade” and presents some commonly used methods in discrete mathematics while the other (shorter) appendix contains definitions, terminology, and notation. Secondly, and in keeping with a quintessential trait of Erdős’ approach to mathematics by starting with simply stated questions, the entry point of every chapter can be understood by an undergraduate student with one course in discrete mathematics.
- •
Chapter 1 begins with a statement of Bertrand’s postulate, given above, and Erdős’ elementary proof.
- •
Chapter 2 begins with a theorem of Esther Klein that given any set of five points in the plane no three of which are collinear, it is always possible to select a fourth point such that the four points are the vertices of a convex quadrilateral.
- •
Chapter 3 begins with two versions of the same problem that appeared in the Eötvös Mathematics Competition in 1947 and the Putnam Mathematical Competition in 1953. In the former, it was posed as follows: “Prove that in any group of six people, either there are three people who know one another or three people who do not know one another. Assume ‘knowing’ is a symmetric relation” (p. 36).
- •
Chapter 4 begins with a definition of a delta-system, a family of sets such that the intersection of any two sets in the family is always the same.
- •
Chapter 5 begins with Sperner’s Theorem: Let be a set with elements and a family of subsets such that for any two subsets in neither is contained in the other. Then contains at most elements with equality if and only if consists of all subsets of with or elements.
- •
Chapter 6 begins with a two-color version of van der Waerden’s Theorem: for every positive integer there is a number such that if the integers were colored either red or white there must be an arithmetic progression of distinct terms which are all the same color.
- •
Chapter 7 begins with the statement of Turán’s Theorem that the graph with the most number of edges having no clique of size is the complete graph whose -partite parts have sizes as close to equal as possible.
- •
Chapter 8 begins with the Friendship Theorem of Erdős, Rényi, and Sós. The theorem says that if every two vertices in a finite graph have exactly one common neighbor, then some vertex of is adjacent to every vertex of except itself.
- •
Chapter 9 begins with an introduction to the chromatic number of a graph and graph planarity via a brief history of what is now the Four Color Theorem.
- •
Chapter 10 begins by defining the “probability that a random graph with vertices and edges has some property” as the ratio between the number of such graphs with the property and the total number of graphs with vertices and edges, which is (p. 151).
- •
Chapter 11 begins again with Turán’s Theorem, though stated differently.
The subtitle of the book is A Simple Introduction. I agree that each chapter does indeed have a simple introduction, given the graduate-level writing of this book. However, it quickly becomes out-of-reach for all but the best undergraduates. Upon finishing the book, I found myself wishing Chvátal had also written an undergraduate version, complete with the stories and photos, to inspire students to study discrete mathematics!
The Man Behind the Mathematics
The mathematics, though, is only part of the story. The photos and stories of Erdős transform this work from a textbook about a man’s work to a tribute to the man himself. In no way do the stories presented comprise a full biography of Erdős; the final appendix includes lists of articles, books, films, and websites on Erdős and his mathematical oeuvre, including a link to a declassified FBI file. Chvátal’s anecdotes paint a picture of Erdős only he could make. As he writes in the preface, “I have been one of the blind men holding onto an elephant, and these vignettes form my report on what I felt.” These shared memories show how Erdős worked, his charm, his humility, his eccentricities, his political views, and his humor.
As an undergraduate, I spent one semester in Hungary, studying in the Budapest Semesters in Mathematics (BSM) program, which Erdős helped get off the ground in the 1980s. One of my favorite classes was Advanced Combinatorics taught by András Gyárfás, a frequent collaborator of Erdős. This course was my true introduction to the work of Paul Erdős. Of course, we covered many of the topics found in this book at an undergraduate level. But what I remember most about the class was a kind of excitement that I had never felt before in any classroom. I recall a passionate yet patient teacher, and classmates who became collaborators as we put forth efforts to discover theorems on our own.
Something about my understanding of mathematics changed during my time in Budapest. Prior to attending this program, I had a misguided ambition to be the best mathematician among my peers, which had taken some of the enjoyment of mathematics away. I was chasing recognition rather than results. But when I arrived in Budapest and began taking classes I realized two things. First, I simply was not going to be the best student in the program, however one defines “best”. But more importantly, I found mathematics could be fun again. All I needed to do was replace competition with collaboration.
The Discrete Mathematical Charms of Paul Erdős quickly took me back to my days studying in the Budapest Semesters in Mathematics program. Of Erdős’ character, Chvátal writes: “He empathized with people, he was generous with his money, he was generous with his ideas” (p. 49). Naturally, such a man had a welcoming take on doing mathematics. In Chvátal’s words, “He did not rank people by their mathematical achievement. He was not a snob. What is more, he taught us by example that cooperation instead of rivalry is what makes mathematics gratifying, that collaboration with friends is enjoyable, and that new friends can be made through collaboration. This attitude of his was infectious” (p. 16).
This attitude of Erdős is, fittingly, evident in this book. The sheer number of references in each chapter is proof of this. But Erdős’ approach is now widespread in both research and teaching. Many mathematicians I know pursue few single-author works and instead see mathematics as a cooperative pursuit. Further, they mimic this approach in their classrooms by providing ample time for collaboration.
Many works about Erdős dedicate space to his eccentricities and aggravating behaviors. These are documented, too, in Chvátal’s stories, from Erdős’ needing a host almost wherever he traveled because he could not be bothered with many mundane tasks, to Chvátal and his girlfriend being woken up several nights in a row by Erdős using the radio they had gifted him for Christmas.
Common, too, are stories of his brilliance. Chvátal writes, “But most people eventually climb to a level where a rude awakening lurks: suddenly the natural order of the universe breaks down and you are no longer the smartest kid on the block. The later disenchantment comes, the more it hurts. Paul Erdős never suffered this shock” (p. 16). On a more personal level, Chvátal amusingly recalls the end of a short-lived romantic relationship. Erdős was in town and Chvátal chose to spend the evening with him rather than his girlfriend. This choice led not only to the end of Chvátal’s relationship with his girlfriend, but also to his second joint paper with Erdős.
The stories also aim to show Erdős’ humanity. Chvátal recounts how Erdős’ collaborative spirit went out the window when a ping-pong table was around. How the loss of his mother profoundly affected him. And how Erdős once asked him, while he was driving over 100 miles per hour, why he was going so slowly. Chvátal takes aim at the title (but not content) of a best-selling, award-winning biography of Erdős by Paul Hoffman called The Man Who Loved Only Numbers [1], going so far as to say “[t]he title of that book is clear libel” (p. 123).
Erdős has inspired countless works, including research articles, tributes, books, and movies, undoubtedly due in part to his gregarious approach to mathematics. He wrote over 1500 papers, had more than 500 collaborators, and was a titan of 20th-century mathematics. The two most well-known biographies of Erdős are Hoffman’s The Man Who Loved Only Numbers [1] and Bruce Schechter’s My Brain is Open: The Mathematical Journeys of Paul Erdős [2], both written for a general audience. So too are the George Csicsery films N is a Number: A Portrait of Paul Erdős [3] and Erdős 100 Plus [4]. Chvátal never attempts to recount Erdős’ life in this book. He instead chronicles some of Erdős’ most important contributions to discrete mathematics. There are many touching short tributes to Erdős written by other collaborators (for instance, the moving Reminiscences of Paul Erdős written by Melvin Henriksen is freely-available at https://www.maa.org/reminiscences-of-paul-erdos). Chvátal’s book, mathematics removed, shows the deep reverence to Erdős apparent in these writings. Fan Chung and Ronald Graham’s Erdős on Graphs: His Legacy of Unsolved Problems [5] is perhaps most similar to this book, as it is also geared towards researchers and ends with a chapter of stories on Erdős. However, I should emphasize that in no way is Chvátal rewriting Chung and Graham’s book; they each have a different mathematical focus and, of course, different Erdős anecdotes.
In the introduction, Chvátal mentions that he has left out the Lovász Local Lemma and Szemerédi’s Regular Partition Lemma (p. 2). He also makes choices in each chapter about which results and proofs to include or omit. With the eleven chapters spanning fewer than 200 pages, these omissions are understandable, especially in light of its origins as a series of lecture notes. The book can, of course, be used as a graduate-level textbook. But it is far more than that. The Discrete Mathematical Charms of Paul Erdős is a phenomenal reference for discrete mathematicians and a “simple introduction” to discrete mathematics for any mathematician with the desire to learn about the work and life of Paul Erdős.
References
- [1]
- Paul Hoffman, The man who loved only numbers: The story of Paul Erdős and the search for mathematical truth, Hyperion Books, New York, 1998. MR1666054,
Show rawAMSref
\bib{1}{book}{ label={1}, author={Hoffman, Paul}, title={The man who loved only numbers}, subtitle={The story of Paul Erd\H {o}s and the search for mathematical truth}, publisher={Hyperion Books, New York}, date={1998}, pages={viii+302}, isbn={0-7868-6362-5}, review={\MR {1666054}}, }
- [2]
- Bruce Schechter, My brain is open: The mathematical journeys of Paul Erdős, Simon & Schuster, New York, 1998. MR1638921,
Show rawAMSref
\bib{2}{book}{ label={2}, author={Schechter, Bruce}, title={My brain is open}, subtitle={The mathematical journeys of Paul Erd\H {o}s}, publisher={Simon \& Schuster, New York}, date={1998}, pages={224}, isbn={0-684-84635-7}, isbn={0-684-85980-7}, review={\MR {1638921}}, }
- [3]
- George Paul Csicsery, N is a number: A portrait of Paul Erdős, George Paul Csicsery, Oakland, CA; distributed by A K Peters, Ltd., Natick, MA, 1993. MR1660995,
Show rawAMSref
\bib{3}{book}{ label={3}, author={Csicsery, George Paul}, title={N is a number}, subtitle={A portrait of Paul Erd\H {o}s}, publisher={George Paul Csicsery, Oakland, CA; distributed by A K Peters, Ltd., Natick, MA}, date={1993}, pages={1 videocassette (NTSC; 1/2 inch; VHS) (57 min.); sd., col}, isbn={1-56881-088-1}, review={\MR {1660995}}, }
- [4]
- G. Csicsery, Director, Erdős 100 Plus [Film], USA: Zala Films, 2013.
- [5]
- Fan Chung and Ron Graham, Erdős on graphs: His legacy of unsolved problems, A K Peters, Ltd., Wellesley, MA, 1998. MR1601954,
Show rawAMSref
\bib{5}{book}{ label={5}, author={Chung, Fan}, author={Graham, Ron}, title={Erd\H {o}s on graphs}, subtitle={His legacy of unsolved problems}, publisher={A K Peters, Ltd., Wellesley, MA}, date={1998}, pages={xiv+142}, isbn={1-56881-079-2}, isbn={1-56881-111-X}, review={\MR {1601954}}, }
Credits
Book cover is reproduced with permission of Cambridge University Press through PLSclear.
Figure 1 is courtesy of Adrian Bondy.
Figure 2 is by George Csicsery for his film N is a Number (1993). All rights reserved.
Photo of Ranjan Rohatgi is courtesy of Weeping Willow Photography/Kayla Holdread.