Extremal Combinatorics With Applications in Computer Science /

• Main Author: Jukna, Stasys (Author)
• Corporate Author: SpringerLink (Online service)
• Format: Electronic eBook
• Language: English
• Published: Berlin, Heidelberg : Springer Berlin Heidelberg, 2011.
• Series: Texts in Theoretical Computer Science. An EATCS Series,
• Subjects: Computer science.; Computers.; Computer science > Mathematics.; Computer mathematics.; Number theory.; Combinatorics.; Computer Science.; Theory of Computation.; Number Theory.; Discrete Mathematics in Computer Science.; Computational Mathematics and Numerical Analysis.

This book is a concise, self-contained, up-to-date introduction to extremal combinatorics for nonspecialists. There is a strong emphasis on theorems with particularly elegant and informative proofs, they may be called gems of the theory. The author presents a wide spectrum of the most powerful combi...

Table of Contents:

• 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 Moment Method
• The Entropy Function
• Random Walks
• Derandomization
• Ramseyan Theorems for Numbers
• The Hales–Jewett Theorem
• Applications in Communications Complexity
• References
• Index.