This book is a concise, self-contained, up-to-date introduction to extremal combinatorics for nonspecialists. A strong emphasis is made on theorems with particularly elegant and informative proofs which may be called gems of the theory. A wide spectrum of the most powerful combinatorial tools is presented: methods of extremal set theory, the linear algebra method, the probabilistic method, and fragments of Ramsey theory. A thorough discussion of some recent applications to computer science conveys the relevance and inherent usefulness of these methods in problems outside combinatorics. á . No special combinatorial or algebraic background is assumed, all necessary elements of linear algebra and discrete probability are introduced before their combinatorial applications.Aimed primarily as an introductory text for graduate students, it also provides a compact source of modern extremal combinatorics for researchers in computer science and other fields of discrete mathematics. The book is clearly organized into five parts, with 27 chapters, each devoted to a particular proof technique. The chapters are completed with over 300 exercises of varying difficulty, and hints to their solution. á . This second edition has been extended with substantial new material, and has been revised and updated throughout. It offers three new chapters about expander graphs and eigenvalues, the polynomial method and error-correcting codes. Most of the remaining chapters also includenew material, such as the Kruskal—Katona theorem about shadows, the Lovász—Stein theorem about coverings, large cliques in dense graphs without induced 4-cycles, a new lower bounds argument for monotone formulas, Dvir's solution of finite field Kakeya's conjecture, Moser's algorithmic version of the Lovász Local Lemma, Schöning's algorithm for 3-SAT, the Szemerédi—Trotter theorem about the number of point-line incidences, and applications of expander graphs in extremal number theory, and some other results. Also, some proofs have been shortened and new exercises added. á . No special combinatorial or algebraic background is assumed, all necessary elements of linear algebra and discrete probability are introduced before their combinatorial applications. Aimed primarily as an introductory text for graduate students, it also provides a compact source of modern extremal combinatorics for researchers in computer science and other fields of discrete mathematics. The book is clearly organized into five parts, with 27 chapters, each devoted to a particular proof technique. The chapters are completed with over 300 exercises of varying difficulty, and hints to their solution. á . This second edition has been extended with substantial newmaterial, and has been revised and updated throughout. It offers three new chapters about expander graphs and eigenvalues, the polynomial method and error-correcting codes. Most of the remaining chapters also include new material, such as the Kruskal—Katona theorem INDICE: Preface. Prolog: What this Book Is About. Notation. Counting. Advanced Counting. Probabilistic Counting. The Pigeonhole Principle. Systems of Distinct Representatives. Sunflowers. Intersecting Families. Chains and Antichains. Blocking Sets and the Duality. Density and Universality. Witness Sets and Isolation. Designs. The Basic Method. Orthogonality and Rank Arguments. Eigenvalues and Graph Expansion. The Polynomial Method. Combinatorics of Codes. Linearity of Expectation. The Lovász Sieve. The Deletion Method. The Second MomentMethod. The Entropy Function. Random Walks. Derandomization. Ramseyan Theorems for Numbers. The Hales–Jewett Theorem. Applications in Communications Complexity. References. Index.
- ISBN: 978-3-642-17363-9
- Editorial: Springer Berlin Heidelberg
- Encuadernacion: Cartoné
- Páginas: 401
- Fecha Publicación: 28/01/2011
- Nº Volúmenes: 1
- Idioma: Inglés