Ebook: Extremal Combinatorics: With Applications in Computer Science

---

Content:
Front Matter....Pages I-XVII
Prolog: What This Book Is About....Pages 1-4
Notation....Pages 5-8
Front Matter....Pages 9-9
Counting....Pages 11-22
Advanced Counting....Pages 23-31
The Principle of Inclusion and Exclusion....Pages 32-36
The Pigeonhole Principle....Pages 37-54
Systems of Distinct Representatives....Pages 55-64
Colorings....Pages 65-76
Front Matter....Pages 77-77
Sunflowers....Pages 79-88
Intersecting Families....Pages 89-96
Chains and Antichains....Pages 97-108
Blocking Sets and the Duality....Pages 109-132
Density and Universality....Pages 133-142
Witness Sets and Isolation....Pages 143-152
Designs....Pages 153-166
Front Matter....Pages 167-167
The Basic Method....Pages 169-190
Orthogonality and Rank Arguments....Pages 191-204
Span Programs....Pages 205-218
Front Matter....Pages 219-219
Basic Tools....Pages 221-228
Counting Sieve....Pages 229-236
Front Matter....Pages 219-219
The Lov?sz Sieve....Pages 237-244
Linearity of Expectation....Pages 245-262
The Deletion Method....Pages 263-272
The Second Moment Method....Pages 273-278
The Entropy Function....Pages 279-285
Random Walks....Pages 286-298
Randomized Algorithms....Pages 299-306
Derandomization....Pages 307-318
Front Matter....Pages 319-319
Ramsey’s Theorem....Pages 321-328
Ramseyan Theorems for Numbers....Pages 329-336
The Hales-Jewett Theorem....Pages 337-350
Epilog: What Next?....Pages 351-352
Back Matter....Pages 353-378

---

Content:
Front Matter....Pages I-XVII
Prolog: What This Book Is About....Pages 1-4
Notation....Pages 5-8
Front Matter....Pages 9-9
Counting....Pages 11-22
Advanced Counting....Pages 23-31
The Principle of Inclusion and Exclusion....Pages 32-36
The Pigeonhole Principle....Pages 37-54
Systems of Distinct Representatives....Pages 55-64
Colorings....Pages 65-76
Front Matter....Pages 77-77
Sunflowers....Pages 79-88
Intersecting Families....Pages 89-96
Chains and Antichains....Pages 97-108
Blocking Sets and the Duality....Pages 109-132
Density and Universality....Pages 133-142
Witness Sets and Isolation....Pages 143-152
Designs....Pages 153-166
Front Matter....Pages 167-167
The Basic Method....Pages 169-190
Orthogonality and Rank Arguments....Pages 191-204
Span Programs....Pages 205-218
Front Matter....Pages 219-219
Basic Tools....Pages 221-228
Counting Sieve....Pages 229-236
Front Matter....Pages 219-219
The Lov?sz Sieve....Pages 237-244
Linearity of Expectation....Pages 245-262
The Deletion Method....Pages 263-272
The Second Moment Method....Pages 273-278
The Entropy Function....Pages 279-285
Random Walks....Pages 286-298
Randomized Algorithms....Pages 299-306
Derandomization....Pages 307-318
Front Matter....Pages 319-319
Ramsey’s Theorem....Pages 321-328
Ramseyan Theorems for Numbers....Pages 329-336
The Hales-Jewett Theorem....Pages 337-350
Epilog: What Next?....Pages 351-352
Back Matter....Pages 353-378
....