Extremal Combinatorics

With Applications in Computer Science
1. Auflage 2001
ISBN: 978-3-540-66313-3
Verlag: Springer

Buch, Englisch, 375 Seiten, Format (B × H): 155 mm x 235 mm, Gewicht: 706 g

Reihe: Texts in Theoretical Computer Science. An EATCS Series

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.

Zielgruppe

Research

Autoren/Hrsg.

Jukna, Stasys

Fachgebiete

• Mathematik | Informatik Mathematik Stochastik Wahrscheinlichkeitsrechnung
• Mathematik | Informatik Mathematik Numerik und Wissenschaftliches Rechnen Angewandte Mathematik, Mathematische Modelle
• Mathematik | Informatik Mathematik Algebra Lineare und multilineare Algebra, Matrizentheorie

Inhaltsverzeichnis

Introduction.- I. The Classis: Counting.- The Pigeon-Hole Principle.- Principle of Inclusion and Exclusion.- Systems of Distinct Representatives.- Colorings.- Chains and Antichains.- Intersecting Families.- Covers and Transversals.- Sunflowers.- Density and Universality.- Designs.- Witness Sets.- Isolation Lemmas.- II. The Linear Algebra Method: Basic Method.- The Polynomial Technique.- Monotone Span Programs.- III. The Probabilistic Method: Basic Tools.- Counting Sieve.- Lovász Sieve.- Linearity of Expectation.- The Deletion Method.- Second Moment Method.- Bounding of Large Deviations.- Randomized Algorithms.- Derandomization.- The Entropy Function.- Random Walks and Search Problems.- IV. Fragments of Ramsey Theory: Ramsey's Theorem.- The Hales-Jewett Theorem.- Epilogue: What Next?- Bibliography.- Index.