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

Prolog: What This Book Is About.- Notation.- 1. Counting.- 2. Advanced Counting.- 3. The Principle of Inclusion and Exclusion.- 4. The Pigeonhole Principle.- 5. Systems of Distinct Representatives.- 6. Colorings.- 7. Sunflowers.- 8. Intersecting Families.- 9. Chains and Antichains.- 10. Blocking Sets and the Duality.- 11. Density and Universality.- 12. Witness Sets and Isolation.- 13. Designs.- 14. The Basic Method.- 15. Orthogonality and Rank Arguments.- 16. Span Programs.- 17. Basic Tools.- 18. Counting Sieve.- 19. The Lovász Sieve.- 20. Linearity of Expectation.- 21. The Deletion Method.- 22. The Second Moment Method.- 23. The Entropy Function.- 24. Random Walks.- 25. Randomized Algorithms.- 26. Derandomization.- 27. Ramsey's Theorem.- 28. Ramseyan Theorems for Numbers.- 29. The Hales-Jewett Theorem.- Epilog: What Next?.- References.- Name Index.