Extremal Combinatorics

With Applications in Computer Science

Stasys Jukna (Autor)

Buch | Hardcover

XVII, 375 Seiten

2001
Springer Berlin (Verlag)
978-3-540-66313-3 (ISBN)

Infos

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.

Inhalt

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.

Produkt-Details

• Reihe/Serie: Texts in Theoretical Computer Science. An EATCS Series
• Sprache: englisch
• Maße: 155 x 235 mm
• Gewicht: 706 g
• Einbandart: gebunden
• Themenwelt: Mathematik / Informatik ► Informatik
• Schlagworte: combinatorics • Computational Complexity • Discrete Mathematics • Diskrete Mathematik • extremal combinatorics • extremal set theory • Kombinatorik
• ISBN-10: 3-540-66313-4 / 3540663134
• ISBN-13: 978-3-540-66313-3 / 9783540663133
• Zustand: Neuware