Focusing on elegant theorems and informative proofs, this book serves as a concise introduction to extremal combinatorics for nonspecialists. It covers a variety of combinatorial tools, making complex concepts accessible and engaging. The text aims to enhance understanding of extremal problems in combinatorics through clear explanations and a structured approach.
This is a concise, up-to-date introduction to extremal combinatorics for non-specialists. Strong emphasis is made on theorems with particularly elegant and informative proofs which may be called the gems of the theory. A wide spectrum of the most powerful combinatorial tools is presented, including methods of extremal set theory, the linear algebra method, the probabilistic method and fragments of Ramsey theory. A thorough discussion of recent applications to computer science illustrates the inherent usefulness of these methods.
The book presents a thorough examination of fundamental lower-bounds arguments, highlighting significant discoveries from the last twenty years, including the most recent findings. It encompasses a diverse range of models such as circuits, formulas, communication protocols, and branching programs, making it a valuable resource for understanding advancements in computational theory.
The book offers an engaging exploration of tropical circuits as a mathematical framework for dynamic programming (DP). It highlights their relevance in addressing combinatorial and discrete optimization challenges, making complex algorithmic concepts more accessible. Through this unique lens, readers can gain insights into the foundational principles of DP and its applications in various optimization problems.
für Informatiker
Studierende, die ein Informatikstudium aufnehmen, brauchen zu Beginn vor allem mathematische Grundkenntnisse. Dieser Crashkurs soll Studierenden im ersten Semester helfen, möglichst rechtzeitig diese Fähigkeiten zu erwerben.Durch viele motivierende Beispiele, erklärende Bilder und konkrete Darstellungen weckt das Buch Freude an der Mathematik und sichert den erfolgreichen Einstieg.