While I am currently doing research in analysis and partial differential equations as a Ph.D. student at the University of Tennessee-Knoxville, my love of mathematics was focused in discrete mathematics, particularly combinatorics, during the earlier years of my undergraduate study. This was in part due to a research topics course I took during my freshmen year of college at Carnegie Mellon with visiting professor Steven Miller, and in part due to my experience competing in competitions such as ARML and the Putnam. Nonetheless, my math textbook collection grew to include various discrete math textbooks, particularly those on combinatorics. To this day, combinatorics is my favorite sub-field of discrete mathematics, and I do have a few papers published at the intersection of number theory and combinatorics.
In this article, I’m going to review a selection of these books that are currently on my bookshelf. I’ll talk about the content covered, the intended audience, and anything in particular I’ve found the book useful for. Since the books have different intended audiences and writing styles, I don’t like to plainly say that one book is better than another. That being said I will list the books in alphabetical order by author last name.
First up we have “A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory” by Miklós Bóna. I bought this book to use as a reference text and as part of a literature review for some enumerative combinatorics research I’ve done, including research towards a paper I submitted as a mentorship effort for an undergraduate student overseas. That being said, this book is accessible to students without any prior discrete math or combinatorics background, so long those students start from the beginning of the book. Knowledge of how to prove mathematical statements by induction is not assumed, because that is the focus of Chapter 2 (Chapter 1 focuses on the Pigeonhole Principle). Most of my time was personally spent studying Chapter 5 (on partitions) and Chapter 8 (generating functions), because those are the topics most pertinent to the research I’ve done to date.
Despite the name of the text, there are additional chapters on graph theory, Ramsey Theory (the study of the existence of patterns of edges and vertices in colored graphs), and theoretical computer science. One other nice feature of this text is a wide gradient of exercises, with regards to difficulty. Exercises that are designed as straightforward applications of definitions and theorems in the text are indicated as such, and the difficulty goes up from there. At the highest level are some problems that aren’t even completely solved and hence can viably form the basis of research projects. That being said, if you use this book as a source of open problems, look elsewhere to make sure the problems haven’t been solved since the publication of the book (in 2011). Solutions are provided to some problems within the book.
The second book I’ll discuss is “Discrete Mathematics: Elementary and Beyond.” I had purchased this as a textbook for the Discrete Mathematics course I took during my second semester as an undergraduate at Carnegie Mellon University.
The topics are fairly similar to those in Bóna’s textbook, but I would more likely pick Lovász’s text as a “first” discrete math text because more care is taken to motivate mathematical concepts and relate them to real-world problems. For instance, the chapter on Fibonacci Numbers opens with a brief discussion on how recursion plays a role in population modeling. There’s also a more conversational tone, which some readers find more inviting.
Some other topics covered in the book include: induction, the Law of Large Numbers, trees, graph matching, Latin squares, and computational complexity. If you pick up this book, feel free to jump around. Many of the chapters don’t depend on each other.
Now we venture into a massive, almost 800-page book on probability. “The Probability Lifesaver” by Steven J. Miller, published by Princeton University Press.
I’ll preface my comments on the content of this book by saying that this book was written by an advisor for much of the research I did as an undergraduate student, and to this day I still work with him on projects, largely as part of a joint mentorship effort for younger students. Anyway, I wanted to buy this book not only as a means of supporting him, but also as an invaluable resource on probability (and combinatorics).
In the book’s preface Miller indicates that this book can be used as a textbook for many different courses, or as a supplementary text. I personally never had to use it for a course, but it became a useful reference as I moved forward with various projects (especially the material on expected value, which I’ve found very useful for my projects). The reason for this quickly becomes clear as you read the introduction and table of contents. This book being so long gives plenty of room to hit on many subjects: discrete and continuous probability, some statistics, and some enumerative combinatorics. Many of the chapters, especially in the second half of the book, utilize calculus in linear algebra. Complex analysis even makes an appearance in a few special places, namely in the discussion of the Central Limit Theorem. Each chapter ends with a wide range of exercises; many of them involve writing proofs, but some involve calculations, either by hand or by using a computer.
While the wide scope of the book makes it usable by students with many different goals and levels of preparation, any book of this nature has one potential pitfall. A student can get overwhelmed if they pick up this book and begin from page one without a plan. I do not believe Miller intends for this book to be read in depth from cover to cover, so if you plan to use it, it’s best to have a specific reason why you want to use it. If this book is a suggested or required text for a course you’re taking, then presumably your professor has done a lot of that planning for you. They’ll tell you what chapters to read, right? I hope so.
Finally, I’m going to briefly discuss the text “Introduction to Graph Theory” by Richard J. Trudeau. I honestly can’t remember what specifically enticed me to purchase this specific book beyond it being a Dover publication. The Dover line of mathematics books combine great value and a concise treatment of various areas of mathematics. This one of course focuses on graph theory.
The end goal of this book is for the reader to understand and appreciate the Königsberg Bridge problem, a problem studied by Euler that motivated much of the study of graph theory. In other words, the problem could not be addressed with mathematical tools or terminology that had been developed prior, so graph theory was developed from the ground up, and Trudeau’s book provides insight on a range of related topics. These topics include planar graphs, graph colorings, Euler’s formula, platonic graphs, and walks along graphs. Every facet of graph theory is very heavy on terminology, and while this book does not shy away from new vocabulary, plentiful pictures are provided alongside it.
So what is the Königsberg Bridge problem? Back in the 18th century, the city of Königsberg had seven bridges spanning three rivers in the city. Architects, mathematicians, and citizens alike wondered if it was possible to cross every bridge once without passing any bridge more than once. In the particular layout of these bridges, the task was in fact impossible. What’s really important, however, is that the bridges and islands constituted a model for some of the most fundamental objects in graph theory: the edges and nodes of a graph. This ultimately invites Trudeau to tell the story of this interesting subject. If you want to pick up a book about graph theory, I wouldn’t say there are any “hard” prerequisites, though familiarity with proof by induction would be helpful. Any first undergraduate mathematics course in proof writing or discrete mathematics will likely cover this.