Discrete Mathematics. By L aszlo Lov asz, graph …

1 Discrete L aszlo Lov asz,J ozef Pelik an and katalin k . , New York, 2003. ISBN entry in Springer sUndergraduate Textsin Mathematicsseries is meant as an introductionto Discrete mathematics , possibly as an alterna-tive to a calculus course for a student s first colle-giate course in mathematics . While the title says Discrete mathematics , the authors admit in thepreface that mostly this is combinatorics andgraph theory with some number theory, probabil-ity and combinatorial geometry mixed in. Whilethe style is informal and the narrative crisp, theauthors still stress the importance of proofs, onlygrudgingly conceding that some necessary resultsmight have proofs beyond the scope of the level of the text would make it most suitablefor upper-division undergraduates, but it mightbe used successfully with sophomores or talentedfreshmen.

2 It might also be suitable as an engag-ing choice for independent first section of the first chapter discussesa fictional party involving seven friends who en-counter, and reason through, several combina-torial problems during the evening s these four pages we briefly, but accurately,consider: the number of edges in the completegraphK7as everybody shakes hands; the numberof circular permutations as the seven are seatedaround a table; the multiplication principle asdance partners are chosen; binomial coefficientsas they purchase lottery tickets, and play a gameof bridge; and multinomial coefficients as theyformulate a small chess tourney. This entertain-ing introduction sets the tone for the remainderof the book, which is written in the kind of leanand lively style that would make the erstwhilereformers of calculus texts green with first and third chapters concentrate oncounting problems, covering most of the variouscombinations of arrangements and distributions,with and without repetition, etc.

3 The secondchapter includes the standard topics of induction,inclusion-exclusion and the pigeonhole , in this introduction to basic combina-torics, there is no discussion of problems thatlead to the Bell or Stirling numbers, or parti-tions of integers. Similarly, there is no discus-sion of methods for solving simple recurrence re-lations. Were these topics to be added, the textcould serve as an excellent introduction to com-binatorics and graph chapters (six in total) cover the basics ofgraph theory, such as Eulerian and Hamiltoniangraphs, trees, planar graphs and coloring. Com-binatorial optimization is introduced via Steinertrees, the traveling salesman problem and topics make this book different? Fromearly on, as might be expected from authors withHungarian roots, the notion of asymptotic analy-sis and probability is woven throughout the , an early chapter titled CombinatorialProbability presents results like the law of largenumbers.

4 The basics of number theory are cov-ered carefully in Chapter 6, and employed prof-itably in the final chapter where notions of com-plexity and cryptography are introduced. Thepenultimate chapter has a good introduction tofinite geometries and designs (dubbed prettycreatures ) and their connections with codingtheory. A chapter on Combinatorics in Geome-try rounds out the collection of atypical are included, sometimes inserted inthe narrative, otherwise they appear at the end ofsections. Every problem has an entry in the An-swers section at the back of the book, and oftenthese are detailed explanations rather than justnumerical final answers. The exercises are not asnumerous as one would like to see in a textbook,and in some cases are too few ( only one prob-lem in the section on inclusion-exclusion).

5 In-structors considering using this text might con-template if they are prepared to supplement theexercises. That said, the exercises seem to be de-signed carefully and the student that works themdiligently will authors intend this book to be an en-gaging introduction to the principal topics cov-ered by the umbrella term of Discrete mathe-matics, and on this score they have succeededadmirably. The text is readable and entertain-ing, without sacrificing any rigor, or cutting anycorners. In the preface they say that the aim ofthis book is not to cover Discrete mathematics indepth. Consistent with this statement, certaindecisions have been made about what to leave inand what to leave out. The title of the book con-tains the subtitle Elementary and Beyond, andin this respect they have also succeeded.

6 Topicssuch as complexity, cryptography, coding theoryand finite geometries give the interested reader aglimpse into more advanced topics that build onthe basic material, and which might be sufficientto whet one s appetite for text is a welcome addition to the collec-tion of undergraduate texts that cover combina-torics and graph theory. Its style and the inclu-sion of nontrivial advanced topics distinguish itfrom many others. With the addition of more ba-sic counting concepts and more high-quality ex-ercises it could be a real standout. It is worthy ofserious consideration by an instructor for use inan appropriate course, or by a curious individualfor independent A. BeezerUniversity of Puget SoundAn edited version of this review was published inSIAM Review45, No.

7 4 (2003) as part of the BookReview section.