| |
| |
| Preface | |
| |
| |
| Acknowledgments | |
| |
| |
| |
| Methods | |
| |
| |
| |
| The Basic Method | |
| |
| |
| |
| The Probabilistic Method | |
| |
| |
| |
| Graph Theory | |
| |
| |
| |
| Combinatorics | |
| |
| |
| |
| Combinatorial Number Theory | |
| |
| |
| |
| Disjoint Pairs | |
| |
| |
| |
| Exercises | |
| |
| |
| The Probabilistic Lens: The Erdos-Ko-Rado Theorem | |
| |
| |
| |
| Linearity of Expectation | |
| |
| |
| |
| Basics | |
| |
| |
| |
| Splitting Graphs | |
| |
| |
| |
| Two Quickies | |
| |
| |
| |
| Balancing Vectors | |
| |
| |
| |
| Unbalancing Lights | |
| |
| |
| |
| Without Coin Flips | |
| |
| |
| |
| Exercises | |
| |
| |
| The Probabilistic Lens: Bregman's Theorem | |
| |
| |
| |
| Alterations | |
| |
| |
| |
| Ramsey Numbers | |
| |
| |
| |
| Independent Sets | |
| |
| |
| |
| Combinatorial Geometry | |
| |
| |
| |
| Packing | |
| |
| |
| |
| Recoloring | |
| |
| |
| |
| Continuous Time | |
| |
| |
| |
| Exercises | |
| |
| |
| The Probabilistic Lens: High Girth and High Chromatic Number | |
| |
| |
| |
| The Second Moment | |
| |
| |
| |
| Basics | |
| |
| |
| |
| Number Theory | |
| |
| |
| |
| More Basics | |
| |
| |
| |
| Random Graphs | |
| |
| |
| |
| Clique Number | |
| |
| |
| |
| Distinct Sums | |
| |
| |
| |
| The Rodl Nibble | |
| |
| |
| |
| Exercises | |
| |
| |
| The Probabilistic Lens: Hamiltonian Paths | |
| |
| |
| |
| The Local Lemma | |
| |
| |
| |
| The Lemma | |
| |
| |
| |
| Property B and Multicolored Sets of Real Numbers | |
| |
| |
| |
| Lower Bounds for Ramsey Numbers | |
| |
| |
| |
| A Geometric Result | |
| |
| |
| |
| The Linear Arboricity of Graphs | |
| |
| |
| |
| Latin Transversals | |
| |
| |
| |
| The Algorithmic Aspect | |
| |
| |
| |
| Exercises | |
| |
| |
| The Probabilistic Lens: Directed Cycles | |
| |
| |
| |
| Correlation Inequalities | |
| |
| |
| |
| The Four Functions Theorem of Ahlswede and Daykin | |
| |
| |
| |
| The FKG Inequality | |
| |
| |
| |
| Monotone Properties | |
| |
| |
| |
| Linear Extensions of Partially Ordered Sets | |
| |
| |
| |
| Exercises | |
| |
| |
| The Probabilistic Lens: Turan's Theorem | |
| |
| |
| |
| Martingales and Tight Concentration | |
| |
| |
| |
| Definitions | |
| |
| |
| |
| Large Deviations | |
| |
| |
| |
| Chromatic Number | |
| |
| |
| |
| Two General Settings | |
| |
| |
| |
| Four Illustrations | |
| |
| |
| |
| Talagrand's Inequality | |
| |
| |
| |
| Applications of Talagrand's Inequality | |
| |
| |
| |
| Kim-Vu Polynomial Concentration | |
| |
| |
| |
| Exercises | |
| |
| |
| The Probabilistic Lens: Weierstrass Approximation Theorem | |
| |
| |
| |
| The Poisson Paradigm | |
| |
| |
| |
| The Janson Inequalities | |
| |
| |
| |
| The Proofs | |
| |
| |
| |
| Brun's Sieve | |
| |
| |
| |
| Large Deviations | |
| |
| |
| |
| Counting Extensions | |
| |
| |
| |
| Counting Representations | |
| |
| |
| |
| Further Inequalities | |
| |
| |
| |
| Exercises | |
| |
| |
| The Probabilistic Lens: Local Coloring | |
| |
| |
| |
| Pseudorandomness | |
| |
| |
| |
| The Quadratic Residue Tournaments | |
| |
| |
| |
| Eigenvalues and Expanders | |
| |
| |
| |
| Quasirandom Graphs | |
| |
| |
| |
| Exercises | |
| |
| |
| The Probabilistic Lens: Random Walks | |
| |
| |
| |
| Topics | |
| |
| |
| |
| Random Graphs | |
| |
| |
| |
| Subgraphs | |
| |
| |
| |
| Clique Number | |
| |
| |
| |
| Chromatic Number | |
| |
| |
| |
| Zero-One Laws | |
| |
| |
| |
| Exercises | |
| |
| |
| The Probabilistic Lens: Counting Subgraphs | |
| |
| |
| |
| The Erdos-Renyi Phase Transition | |
| |
| |
| |
| An Overview | |
| |
| |
| |
| Three Processes | |
| |
| |
| |
| The Galton-Watson Branching Process | |
| |
| |
| |
| Analysis of the Poisson Branching Process | |
| |
| |
| |
| The Graph Branching Model | |
| |
| |
| |
| The Graph and Poisson Processes Compared | |
| |
| |
| |
| The Parametrization Explained | |
| |
| |
| |
| The Subcritical Regimes | |
| |
| |
| |
| The Supercritical Regimes | |
| |
| |
| |
| The Critical Window | |
| |
| |
| |
| Analogies to Classical Percolation Theory | |
| |
| |
| |
| Exercises | |
| |
| |
| The Probabilistic Lens: The Rich Get Richer | |
| |
| |
| |
| Circuit Complexity | |
| |
| |
| |
| Preliminaries | |
| |
| |
| |
| Random Restrictions and Bounded-Depth Circuits | |
| |
| |
| |
| More on Bounded-Depth Circuits | |
| |
| |
| |
| Monotone Circuits | |
| |
| |
| |
| Formulae | |
| |
| |
| |
| Exercises | |
| |
| |
| The Probabilistic Lens: Maximal Antichains | |
| |
| |
| |
| Discrepancy | |
| |
| |
| |
| Basics | |
| |
| |
| |
| Six Standard Deviations Suffice | |
| |
| |
| |
| Linear and Hereditary Discrepancy | |
| |
| |
| |
| Lower Bounds | |
| |
| |
| |
| The Beck-Fiala Theorem | |
| |
| |
| |
| Exercises | |
| |
| |
| The Probabilistic Lens: Unbalancing Lights | |
| |
| |
| |
| Geometry | |
| |
| |
| |
| The Greatest Angle Among Points in Euclidean Spaces | |
| |
| |
| |
| Empty Triangles Determined by Points in the Plane | |
| |
| |
| |
| Geometrical Realizations of Sign Matrices | |
| |
| |
| |
| [epsilon]-Nets and VC-Dimensions of Range Spaces | |
| |
| |
| |
| Dual Shatter Functions and Discrepancy | |
| |
| |
| |
| Exercises | |
| |
| |
| The Probabilistic Lens: Efficient Packing | |
| |
| |
| |
| Codes, Games and Entropy | |
| |
| |
| |
| Codes | |
| |
| |
| |
| Liar Game | |
| |
| |
| |
| Tenure Game | |
| |
| |
| |
| Balancing Vector Game | |
| |
| |
| |
| Nonadaptive Algorithms | |
| |
| |
| |
| Half Liar Game | |
| |
| |
| |
| Entropy | |
| |
| |
| |
| Exercises | |
| |
| |
| The Probabilistic Lens: An Extremal Graph | |
| |
| |
| |
| Derandomization | |
| |
| |
| |
| The Method of Conditional Probabilities | |
| |
| |
| |
| d-Wise Independent Random Variables in Small Sample Spaces | |
| |
| |
| |
| Exercises | |
| |
| |
| The Probabilistic Lens: Crossing Numbers, Incidences, Sums and Products | |
| |
| |
| |
| Graph Property Testing | |
| |
| |
| |
| Property Testing | |
| |
| |
| |
| Testing Colorability | |
| |
| |
| |
| Szemeredi's Regularity Lemma | |
| |
| |
| |
| Testing Triangle-Freeness | |
| |
| |
| |
| Characterizing the Testable Graph Properties | |
| |
| |
| |
| Exercises | |
| |
| |
| The Probabilistic Lens: Turan Numbers and Dependent Random Choice | |
| |
| |
| |
| Bounding of Large Deviations | |
| |
| |
| |
| Chernoff Bounds | |
| |
| |
| |
| Lower Bounds | |
| |
| |
| |
| Exercises | |
| |
| |
| The Probabilistic Lens: Triangle-Free Graphs Have Large Independence Numbers | |
| |
| |
| |
| Paul Erdos | |
| |
| |
| |
| Papers | |
| |
| |
| |
| Conjectures | |
| |
| |
| |
| On Erdos | |
| |
| |
| |
| Uncle Paul | |
| |
| |
| References | |
| |
| |
| Author Index | |
| |
| |
| Subject Index | |