The Probabilistic Method

by Alon, Noga; Spencer, Joel H.

• ISBN13: 9780470170205
• ISBN10: 0470170204
• Edition: 3rd
• Format: Hardcover
• Copyright: 2008-08-11
• Publisher: Wiley-Interscience

Summary

This Third Edition of The Probabilistic Method reflects the most recent developments in the field while maintaining the standard of excellence that established this book as the leading reference on probabilistic methods in combinatorics. Maintaining its clear writing style, illustrative examples, and practical exercises, this new edition emphasizes methodology, enabling readers to use probabilistic techniques for solving problems in such fields as theoretical computer science, mathematics, and statistical physics. The book begins with a description of tools applied in probabilistic arguments, including basic techniques that use expectation and variance as well as the more recent applications of martingales and correlation inequalities. Next, the authors examine where probabilistic techniques have been applied successfully, exploring such topics as discrepancy and random graphs, circuit complexity, computational geometry, and derandomization of randomized algorithms. Sections labeled "The Probabilistic Lens" offer additional insights into the application of the probabilistic approach, and the appendix has been updated to include methodologies for finding lower bounds for Large Deviations. The Third Edition also features: A new chapter on graph property testing, which is a current topic that incorporates combinatorial, probabilistic, and algorithmic techniques An elementary approach using probabilistic techniques to the powerful Szemeredi Regularity Lemma and its applications New sections devoted to percolation and liar games A new chapter that provides a modern treatment of the Erdos-Renyi phase transition in the Random Graph Process Written by two leading authorities in the field, The Probabilistic Method, Third Edition is an ideal reference for researchers in combinatorics and algorithm design who would like to better understand the use of probabilistic methods. The book's numerous exercises and examples also make it an excellent textbook for graduate-level courses in mathematics and computer science.

Author Biography

NOGA ALON, PhD, is Baumritter Professor of Mathematics and Computer Science at Tel Aviv University, Israel. A member of the Israel National Academy of Sciences, Dr. Alon has written over 400 published papers, mostly in the areas of combinatorics and theoretical computer science. He is the recipient of numerous honors in the field, including the Erdös Prize (1989), the Pólya Prize (2000), the Landau Prize (2005), and the Gödel Prize (2005).

JOEL H. SPENCER, PhD, is Professor of Mathematics and Computer Science at the Courant Institute of Mathematical Sciences at New York University and is the cofounder and coeditor of the journal Random Structures and Algorithms. Dr. Spencer has written over 150 published articles and is the coauthor of Ramsey Theory, Second Edition, also published by Wiley.

Table of Contents

Preface	p. xiii
Acknowledgments	p. xv
Methods
The Basic Method	p. 1
The Probabilistic Method	p. 1
Graph Theory	p. 1
Combinatorics	p. 3
Combinatorial Number Theory	p. 9
Disjoint Pairs	p. 10
Exercises	p. 11
The Probabilistic Lens: The Erdos-Ko-Rado Theorem	p. 13
Linearity of Expectation	p. 15
Basics	p. 15
Splitting Graphs	p. 16
Two Quickies	p. 18
Balancing Vectors	p. 19
Unbalancing Lights	p. 21
Without Coin Flips	p. 22
Exercises	p. 23
The Probabilistic Lens: Bregman's Theorem	p. 24
Alterations	p. 27
Ramsey Numbers	p. 27
Independent Sets	p. 29
Combinatorial Geometry	p. 30
Packing	p. 31
Recoloring	p. 32
Continuous Time	p. 35
Exercises	p. 39
The Probabilistic Lens: High Girth and High Chromatic Number	p. 41
The Second Moment	p. 43
Basics	p. 43
Number Theory	p. 44
More Basics	p. 47
Random Graphs	p. 49
Clique Number	p. 53
Distinct Sums	p. 54
The Rodl Nibble	p. 56
Exercises	p. 61
The Probabilistic Lens: Hamiltonian Paths	p. 63
The Local Lemma	p. 67
The Lemma	p. 67
Property B and Multicolored Sets of Real Numbers	p. 70
Lower Bounds for Ramsey Numbers	p. 71
A Geometric Result	p. 73
The Linear Arboricity of Graphs	p. 74
Latin Transversals	p. 78
The Algorithmic Aspect	p. 79
Exercises	p. 82
The Probabilistic Lens: Directed Cycles	p. 83
Correlation Inequalities	p. 85
The Four Functions Theorem of Ahlswede and Daykin	p. 86
The FKG Inequality	p. 89
Monotone Properties	p. 90
Linear Extensions of Partially Ordered Sets	p. 92
Exercises	p. 94
The Probabilistic Lens: Turan's Theorem	p. 95
Martingales and Tight Concentration	p. 97
Definitions	p. 97
Large Deviations	p. 99
Chromatic Number	p. 101
Two General Settings	p. 103
Four Illustrations	p. 107
Talagrand's Inequality	p. 109
Applications of Talagrand's Inequality	p. 113
Kim-Vu Polynomial Concentration	p. 115
Exercises	p. 116
The Probabilistic Lens: Weierstrass Approximation Theorem	p. 117
The Poisson Paradigm	p. 119
The Janson Inequalities	p. 119
The Proofs	p. 121
Brun's Sieve	p. 124
Large Deviations	p. 127
Counting Extensions	p. 129
Counting Representations	p. 130
Further Inequalities	p. 133
Exercises	p. 135
The Probabilistic Lens: Local Coloring	p. 136
Pseudorandomness	p. 139
The Quadratic Residue Tournaments	p. 140
Eigenvalues and Expanders	p. 143
Quasirandom Graphs	p. 149
Exercises	p. 156
The Probabilistic Lens: Random Walks	p. 157
Topics
Random Graphs	p. 161
Subgraphs	p. 162
Clique Number	p. 164
Chromatic Number	p. 166
Zero-One Laws	p. 167
Exercises	p. 175
The Probabilistic Lens: Counting Subgraphs	p. 177
The Erdos-Renyi Phase Transition	p. 179
An Overview	p. 180
Three Processes	p. 182
The Galton-Watson Branching Process	p. 183
Analysis of the Poisson Branching Process	p. 184
The Graph Branching Model	p. 186
The Graph and Poisson Processes Compared	p. 187
The Parametrization Explained	p. 190
The Subcritical Regimes	p. 190
The Supercritical Regimes	p. 191
The Critical Window	p. 194
Analogies to Classical Percolation Theory	p. 197
Exercises	p. 201
The Probabilistic Lens: The Rich Get Richer	p. 203
Circuit Complexity	p. 205
Preliminaries	p. 205
Random Restrictions and Bounded-Depth Circuits	p. 207
More on Bounded-Depth Circuits	p. 211
Monotone Circuits	p. 214
Formulae	p. 217
Exercises	p. 218
The Probabilistic Lens: Maximal Antichains	p. 219
Discrepancy	p. 221
Basics	p. 221
Six Standard Deviations Suffice	p. 223
Linear and Hereditary Discrepancy	p. 226
Lower Bounds	p. 229
The Beck-Fiala Theorem	p. 231
Exercises	p. 232
The Probabilistic Lens: Unbalancing Lights	p. 234
Geometry	p. 237
The Greatest Angle Among Points in Euclidean Spaces	p. 238
Empty Triangles Determined by Points in the Plane	p. 239
Geometrical Realizations of Sign Matrices	p. 241
[epsilon]-Nets and VC-Dimensions of Range Spaces	p. 243
Dual Shatter Functions and Discrepancy	p. 248
Exercises	p. 251
The Probabilistic Lens: Efficient Packing	p. 252
Codes, Games and Entropy	p. 255
Codes	p. 255
Liar Game	p. 258
Tenure Game	p. 260
Balancing Vector Game	p. 261
Nonadaptive Algorithms	p. 264
Half Liar Game	p. 264
Entropy	p. 266
Exercises	p. 271
The Probabilistic Lens: An Extremal Graph	p. 273
Derandomization	p. 275
The Method of Conditional Probabilities	p. 275
d-Wise Independent Random Variables in Small Sample Spaces	p. 280
Exercises	p. 284
The Probabilistic Lens: Crossing Numbers, Incidences, Sums and Products	p. 285
Graph Property Testing	p. 289
Property Testing	p. 289
Testing Colorability	p. 290
Szemeredi's Regularity Lemma	p. 294
Testing Triangle-Freeness	p. 298
Characterizing the Testable Graph Properties	p. 300
Exercises	p. 302
The Probabilistic Lens: Turan Numbers and Dependent Random Choice	p. 303
Bounding of Large Deviations	p. 307
Chernoff Bounds	p. 307
Lower Bounds	p. 315
Exercises	p. 320
The Probabilistic Lens: Triangle-Free Graphs Have Large Independence Numbers	p. 321
Paul Erdos	p. 323
Papers	p. 323
Conjectures	p. 325
On Erdos	p. 326
Uncle Paul	p. 327
References	p. 331
Author Index	p. 345
Subject Index	p. 349
Table of Contents provided by Ingram. All Rights Reserved.