You are here

Discrete Mathematics: Elementary and Beyond

L. Lovasz, J. Pelikan, and K. Vesztergombi
Springer Verlag
Publication Date: 
Number of Pages: 
Undergraduate Texts in Mathematics
[Reviewed by
Michele Intermont
, on

Discrete mathematics is a subject to which no shortage of books have been devoted. It has long been a staple in the mathematics studied and used by computer scientists as well as mathematicians. In light of this, one must certainly ask whether or not another book on the subject belongs on the bookshelf. For many, the answer with respect to this book should be yes.

When this book arrived on my desk, it got buried rather quickly, and after falling onto the back burner, it stayed there for quite some time. Until I started actually reading it. I quite enjoyed carrying this small volume around, reading a section or two at a time. The writing is generally clear and engaging. The material is basic, as one expects from a book in the Undergraduate Texts in Mathematics series, but there is some material "beyond" the elementary. I found myself pleased with how the authors make a point of including developments and applications in their text, in coding theory in particular. I learned of a few results here. For example, there is a discussion of pseudoprimes and of the Miller-Rabin, algorithm which, upon iteration, has an excellent probability of correctly identifying a prime. This result is not new (the authors date it to the late 1970s) but it was new to me. Primality testing is not new either, but it is not standard fare, and lends a nice flavor here. I was also pleased that in several places the authors would state a best known result, and then proceed to state and prove an easier result — one that was within the scope of the book. Surely there are some readers who will find this sort of bait and switch annoying, but I am not one of them. In fact, I felt it added to the introductory nature of the text.

This book does a wonderful job of communicating mathematics as a vibrant field. In many places the authors are willing to remark on the process of doing mathematics, on questions that appear "natural" or "surprising" and of course "elegant". The first paragraph of the chapter entitled Integers, Divisors, and Primes presents a good example of this philosophy in action:

This area of mathematics is called number theory, and it is a truly venerable field: Its roots go back about 2500 years, to the very beginning of Greek mathematics. One might think that after 2500 years of research, one would know essentially everything about the subject. But we shall see that this is not the case: There are very simple, natural questions that we cannot answer; and there are other simple, natural questions to which an answer has been found only in the last few years! (p. 87)

The authors carefully remind us throughout the text that what is convincing does not necessarily constitute a proof. But they do not shy away from first convincing the reader of the likelihood of a result (having usually led the reader to that point skillfully) and then providing a proof.

Lovasz, Pelikan and Vesztergombi's choice of topics does have a more mathematical bent in comparison to some other undergraduate texts at which I looked. The first chapter takes up the topics of sets and counting, but the discussion of unions of sets, intersection of sets, and other such introductory logic is extremely brief. The second chapter leads to the pigeonhole principle, but also discusses estimating the size of numbers, a theme that reappears from time to time throughout the book. The binomial theorem is the main tool of the next chapter, leading quite nicely to identities arising from Pascal's triangle and estimates for sums and quotients of binomial coefficients. Recurrence relations are briefly introduced via the Fibonacci numbers, but attention quickly turns to combinatorial probability and a new chapter. In Chapter Six, the theme is prime numbers. (This is the longest chapter in the text, at about thirty pages.) Graphs and trees, and matching and optimization problems are the themes of the next few chapters. Then there is a foray into planar geometry leading to a discussion of the Four Color Theorem. The last two chapters delve into coding theory and cryptography by introducing projective planes, Steiner systems, etc, on the way to describing the RSA cryptosystem. I'm a sucker for projective planes, as well as cryptography, and was delighted with this selection as a fitting conclusion to the book.

While the choice of topics was to my taste and what made reading this book fun, it will be seen as a drawback by some readers who desire more connection with computer science. For example, there is no mention of boolean logic or automata. Likewise, algorithms are discussed strictly from a mathematical viewpoint — as in the Euclidean Algorithm, as are recurrence relations.

To conclude, in Discrete Mathematics Lovasz, Pelikan and Vesztergombi have succeeded in providing us with a book that is sure to please many readers. It is indeed elementary enough to use as a text in class (although be warned: the solutions to all the exercises are included). But a reader interested in discrete mathematics mostly for the sake of computer science will likely be disappointed, frustrated, or both.

Michele Intermont ( is Associate Professor of Mathematics at Kalamazoo College. Her area of specialty is algebraic topology.