The book is a concise, self-contained and 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 gems of the theory. A wide spectrum of most powerful combinatorial tools is presented: methods of extremal set theory, the linear algebra method, the probabilistic method and fragments of Ramsey theory. A throughout discussion of some recent applications to computer science motivates the liveliness and inherent usefulness of these methods to approach problems outside combinatorics. No special combinatorial or algebraic background is assumed. All necessary elements of linear algebra and discrete probability are introduced before their combinatorial applications. Aimed primarily as an introductory text for graduates, it provides also a compact source of modern extremal combinatorics for researchers in computer science and other fields of discrete mathematics.
Author(s): Stasys Jukna
Series: Texts in Theoretical Computer Science. An EATCS Series
Edition: 1st
Publisher: Springer
Year: 2001
Language: English
Pages: 388
Tags: Discrete Mathematics in Computer Science; Combinatorics; Theory of Computation; Mathematical Logic and Foundations; Computational Mathematics and Numerical Analysis
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
