Discrete mathematics. (English) Zbl 1227.05002

Gallier, Jean

Universitext. Berlin: Springer (ISBN 978-1-4419-8046-5/pbk; 978-1-4419-8047-2/ebook). xiii, 465 p. (2011).

This book is intended to be a textbook for students in computer science, covering basic areas of discrete mathematics. It does not require previous knowledge of any area that is treated, but instead is rather self-contained. At the same time, lots of references to supplementary or more advanced literature are provided, and less basic and more sophisticated problems as well as connections to other areas of science are given. Each chapter closes with a rich collection of exercises, which often include hints to their solution and further explanations.
The first chapter, which is independent of the other chapters of this book, presents a brief introduction into mathematical logic. It contains a short overview of natural deduction systems due to Prawitz and Gentzen and introduces classical and intuitionistic logics. The proof-by-contraposition rule, as well as the induction principle are discussed and problems such as satisfiability, validity, soundness and completeness are elaborated.
The second chapter focuses on the notions of relations and (partial) functions and their basic properties. Following the definition of those notions, the induction principle on \(\mathbb{N}\) is revisited and illustrated by a variety of examples. Moreover, inverse functions are introduced and their existence is related to properties like injectivity, surjectivity and bijectivity. Lastly, a fairly thorough treatment of the concept of the size of a set, including the notions of cardinality, finiteness, infiniteness, countability, the Pigeonhole Principle and the Schröder-Bernstein theorem is provided.
The third chapter deals with the basic concepts of graph theory. Besides elementary notions, such as directed and undirected graphs, paths, cycles and connectedness (including a characterization of connected graphs), also the problem of finding minimal and maximal weight spanning trees is discussed. The algorithms of Kruskal and Prim are presented as possible solutions to this issue.
The fourth chapter presents a brief and elementary introduction to combinatorics. The consideration of various counting problems gives rise to the definition of binomial and multinomial coefficients. Properties and basic facts about these numbers, including the binomial and multinomial formula and binomial identities, such as Vandermonde convolutions, are discussed. Finally, the principle of inclusion-exclusion and Sylvester’s formula respectively the sieve formula as applications of this principle are introduced.
The fifth chapter is concerned with the study of partial orders and equivalence relations and their properties. The induction principle is extended from \(\mathbb{N}\) to the more general setting of well-founded sets. Several applications, including the unique prime factorization theorem over \(\mathbb{Z}\) and properties of Fibonacci and Lucas numbers, are provided. The second half of this chapter contains an introduction to public key cryptography and to RSA, using formerly developed concepts and versions of the Euclidean algorithm. This chapter, also introduces partial orders with additional properties, e.g., (distributive) lattices, Boolean and Heyting algebras and presents some connections to Chapter 1.
Building on Chapter 3, the sixth chapter treats graph theoretic concepts on a more advanced level. The discussion covers cocycles and cotrees, flows and tensions, the incidence and the adjaceny matrix of a graph, Eulerian and Hamiltonian cycles (including the Königsberg bridge problem), network flow problems, e.g., the max-flow min-cut Theorem, matchings with a focus on bipartite graphs, some facts about colorings and the chromatic number of a graph, the characterization of planar graphs due to Kuratowski and some further topics.

Reviewer: Martina Kubitzke (Wien)

MSC:

05-01	Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics
05Axx	Enumerative combinatorics
05Cxx	Graph theory
06Axx	Ordered sets
06Dxx	Distributive lattices
68R05	Combinatorics in computer science
68R10	Graph theory (including graph drawing) in computer science
97E30	Logic (educational aspects)
03Bxx	General logic
97K10	Comprehensive works on combinatorics, graph theory, and probability (educational aspects)

Keywords:

proof principles; classical logic; functions and relations; graph theory; directed and undirected graphs; matchings; incidence and adjacency matrix; permutations; multinomial coefficients; Principle of Inclusion-Exclusion; Counting Problems; partial orders; lattices; prime factorization; RSA