Diekert V., Kufleitner M., Rosenberger G., Hertrampf U. Elements of Discrete Mathematics: Numbers and Counting, Groups, Graphs, Orders and Lattices

Berlin: Walter de Gruyter, 2023. - 280 p. - ISBN 3111060691.This book is based on the courses Discrete Mathematics and Concrete Mathematics for master students in Computer Science and Mathematics at the University of Stuttgart, and in parts on the course Linear Algebra and Algebraic Structures for Computer Scientists at the University of Dortmund. These courses were held successfully over many years. Experiences of these courses had an essential influence on the selection of the material, as well as the presentation.
The idea of this book is to convey essential elements of discrete mathematics needed to work with modern developments of the information era in a mathematically competent manner. The English edition of this book covers the material of its German original, but there is also new material. For example, we introduced the first chapter about algebraic structures, which are used throughout our book and in many other areas of Computer Science, such as design and analysis of efficient algorithms or hardware and software verification. A chapter on discrete probability provides what we need here. Then we go to the heart of discrete mathematics, including combinatorics and generating functions. Later chapters are rather independent of each other and can be read in any order. For example, there is a new and more advanced chapter on group actions. We briefly discuss p-groups and nilpotent groups which are important in many applications. As a byproduct of earlier results, we also show the simplicity of alternating groups. Special attention is paid to graph theory. The corresponding chapter contains various algorithms, ranging from bipartite matching to the planar separator theorem. Finally, we deal with order structures and lattices, as well as Boolean functions and circuits. Exercises in this book have a high priority. We also provide solutions to all exercises, but, of course, in order to keep the learning efficient as high as possible, it is not recommended to fall back on the solutions too quickly.
We provide complete proofs for all important statements, and we refrain from excuses like “This would go far beyond the scope of this book” (!). This book supplements and deepens the basics and demonstrates possible applications. Also some topics that go beyond the standard material are covered. In many places we used original literature that has not yet been published in textbooks.True PDF