Extremal Combinatorics: With Applications in Computer Science

✍ Scribed by Stasys Jukna (auth.)

• Publisher: Springer
• Year: 2011
• Tongue: English
• Leaves: 412
• Edition: 2
• Category: Library

✦ Table of Contents

Front Matter....Pages I-XXIII
Front Matter....Pages 1-1
Counting....Pages 3-22
Advanced Counting....Pages 23-39
Probabilistic Counting....Pages 41-51
The Pigeonhole Principle....Pages 53-75
Systems of Distinct Representatives....Pages 77-86
Front Matter....Pages 87-87
Sunflowers....Pages 89-98
Intersecting Families....Pages 99-106
Chains and Antichains....Pages 107-118
Blocking Sets and the Duality....Pages 119-134
Density and Universality....Pages 135-154
Witness Sets and Isolation....Pages 155-163
Designs....Pages 165-176
Front Matter....Pages 177-177
The Basic Method....Pages 179-196
Orthogonality and Rank Arguments....Pages 197-212
Eigenvalues and Graph Expansion....Pages 213-222
The Polynomial Method....Pages 223-236
Combinatorics of Codes....Pages 237-251
Front Matter....Pages 253-253
Linearity of Expectation....Pages 255-278
The Lovász Sieve....Pages 279-291
The Deletion Method....Pages 293-302
Front Matter....Pages 253-253
The Second Moment Method....Pages 303-312
The Entropy Function....Pages 313-326
Random Walks....Pages 327-339
Derandomization....Pages 341-353
Front Matter....Pages 355-355
Ramseyan Theorems for Numbers....Pages 357-369
The Hales–Jewett Theorem....Pages 371-377
Applications in Communication Complexity....Pages 379-391
Back Matter....Pages 393-411

✦ Subjects

Computational Mathematics and Numerical Analysis