×

Discrete mathematics. Elementary and beyond. (English) Zbl 1017.00002

Undergraduate Texts in Mathematics. New York, NY: Springer. ix, 290 p. (2003).
This book is an excellent introduction to a lot of problems of discrete mathematics. The aim of the book is not cover discrete mathematics in depth. The authors discuss a number of selected results and methods, mostly from the areas of combinatorics and graph theory with a little elementary number theory, probability, and combinatorial geometry. Chapters 1-5 are devoted essentially to the combinatorics (the numbers of subsets of a given size, inclusion-exclusion principle, pigeonholes principle, binomial coefficients and Pascal triangle, Fibonacci numbers, combinatorial probability). Chapter 6 includes elements of number theory (divisibility of integers, primes numbers, Fermat’s “little” theorem, the Euclidean algorithm, congruences).
The next chapters s follows: 7. Graphs (even and odd degrees, paths, cycles, and connectivity, Eulerian walks and Hamilton cycles); 8. Trees (how to define trees, how to grow trees, how to count trees, the number of unlabeled trees); 9. Finding the optimum (finding the best tree, the traveling salesman problem); 10. Matchings in graphs (a dancing problem, another matching problem, the main theorem, how to find a perfect matching); 11. Combinatorics in geometry (intersections of diagonals, counting regions, convex polygons); 12. Euler’s formula (a planet under attack, planar graphs, Euler’s formular for polyhedra); 13. Coloring maps and graphs (coloring regions with two colors, coloring graphs with two colors, coloring graphs with many colors, map coloring and the four color theorem); 14. Finite geometries, codes, Latin squares, and other pretty creatures; 15. A glimpse of complexity and cryptography.
This book is appealed to a broad rang of readers, including students and post-graduate students, teachers of mathematics, mathematical amateurs. The authors use proofs and problem solving to help students understand the solutions to problems. In addition, there are numerous examples, figures and exercises spread throughout the book.

MSC:

00A05 Mathematics in general
05-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics
11-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to number theory
51-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to geometry
05A05 Permutations, words, matrices
05A10 Factorials, binomial coefficients, combinatorial functions
05C05 Trees
05C45 Eulerian and Hamiltonian graphs
PDFBibTeX XMLCite