Extremal combinatorics. With applications in computer science (Q4255576)

This book presents several important parts of combinatorics with emphasis to methods for solving extremal problems. Some interesting applications in theoretical computer science are included. The book is divided into 5 parts: 1. The classics (counting, advanced counting, the principle of inclusion and exclusion, the pigeonhole principle, systems of distinct representatives, colorings), 2. Extremal set theory (sunflowers, intersecting families, chains and antichains, blocking sets and the duality, density and universality, witness sets and isolation, designs), 3. The linear algebra method (the basic method, orthogonality and rank arguments, span programs), 4. The probabilistic method (basic tools, counting sieve, the Lovász sieve, linearity of expectation, the deletion method, the second moment method, the entropy function, random walks, randomized algorithms, derandomization), 5. Fragments of Ramsey theory (Ramsey's theorem, Ramseyan theorems for numbers, the Hales-Jewitt theorem). As written in the preface, the text is indeed self-contained and the chapters are almost independent. More than 300 exercises with short hints but up to some sketches without proofs are included. The presentation is clear and sound. The book is not only valuable for students and teachers, but also for researchers working in discrete mathematics or theoretical computer science. Meanwhile, there exist already several introductory textbooks, problem books, and monographs in this area. Thus intersections with other books cannot be avoided and the choice of subjects and references must clearly depend on the author's taste and area of research. For example, linear programming and flow theoretic methods are not included, and in the large part on extremal set theory the Kruskal-Katona theorem is not mentioned. But in any case the book should be considered as a contribution in building a bridge between combinatorics and the theory of computing.