product iamge

The Probabilistic Method

This document was uploaded by one of our users. The uploader already confirmed that they had the permission to publish it. If you are author/publisher or own the copyright of this documents, please report to us by using this DMCA report form.

Download
Search on Amazon

Simply click on the Download Book button.

Yes, Book downloads on Ebookily are 100% Free.

Sometimes the book is free on Amazon As well, so go ahead and hit "Search on Amazon"

Praise for the Second Edition:

"Serious researchers in combinatorics or algorithm design will wish to read the book in its entirety...the book may also be enjoyed on a lighter level since the different chapters are largely independent and so it is possible to pick out gems in one's own area..." —Formal Aspects of Computing

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 Szemerédi Regularity Lemma and its applications

  • New sections devoted to percolation and liar games

  • A new chapter that provides a modern treatment of the Erdös-Rényi 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(s): Noga Alon, Joel H. Spencer
Series: Wiley-Interscience Series in Discrete Mathematics and Optimization
Edition: 3
Publisher: Wiley-Interscience
Year: 2008

Language: English
Pages: 374

The Probabilistic Method......Page 5
Contents......Page 9
PREFACE......Page 15
ACKNOWLEDGMENTS......Page 17
PART I METHODS......Page 19
1.1 The Probabilistic Method......Page 21
1.2 Graph Theory......Page 23
1.3 Combinatorics......Page 27
1.4 Combinatorial Number Theory......Page 29
1.5 Disjoint Pairs......Page 30
1.6 Exercises......Page 31
The Probabilistic Lens: The Erdös–Ko–Rado Theorem......Page 33
2.1 Basics......Page 35
2.2 Splitting Graphs......Page 36
2.3 Two Quickies......Page 38
2.4 Balancing Vectors......Page 39
2.5 Unbalancing Lights......Page 41
2.6 Without Coin Flips......Page 42
2.7 Exercises......Page 43
The Probabilistic Lens: Brégman’s Theorem......Page 44
3.1 Ramsey Numbers......Page 47
3.2 Independent Sets......Page 49
3.3 Combinatorial Geometry......Page 50
3.4 Packing......Page 51
3.5 Recoloring......Page 52
3.6 Continuous Time......Page 55
3.7 Exercises......Page 59
The Probabilistic Lens: High Girth and High Chromatic Number......Page 61
4.1 Basics......Page 63
4.2 Number Theory......Page 64
4.3 More Basics......Page 67
4.4 Random Graphs......Page 69
4.5 Clique Number......Page 73
4.6 Distinct Sums......Page 74
4.7 The Rödl Nibble......Page 76
4.8 Exercises......Page 81
The Probabilistic Lens: Hamiltonian Paths......Page 83
5.1 The Lemma......Page 87
5.2 Property B and Multicolored Sets of Real Numbers......Page 90
5.3 Lower Bounds for Ramsey Numbers......Page 91
5.4 A Geometric Result......Page 93
5.5 The Linear Arboricity of Graphs......Page 94
5.6 Latin Transversals......Page 98
5.7 The Algorithmic Aspect......Page 99
5.8 Exercises......Page 102
The Probabilistic Lens: Directed Cycles......Page 103
6 Correlation Inequalities......Page 105
6.1 The Four Functions Theorem of Ahlswede and Daykin......Page 106
6.2 The FKG Inequality......Page 109
6.3 Monotone Properties......Page 110
6.4 Linear Extensions of Partially Ordered Sets......Page 112
6.5 Exercises......Page 114
The Probabilistic Lens: Turán’s Theorem......Page 115
7.1 Definitions......Page 117
7.2 Large Deviations......Page 119
7.3 Chromatic Number......Page 121
7.4 Two General Settings......Page 123
7.5 Four Illustrations......Page 127
7.6 Talagrand's Inequality......Page 129
7.7 Applications of Talagrand's Inequality......Page 133
7.8 Kim–Vu Polynomial Concentration......Page 135
7.9 Exercises......Page 136
The Probabilistic Lens: Weierstrass Approximation Theorem......Page 137
8.1 The Janson Inequalities......Page 139
8.2 The Proofs......Page 141
8.3 Brun's Sieve......Page 144
8.4 Large Deviations......Page 147
8.5 Counting Extensions......Page 149
8.6 Counting Representations......Page 150
8.7 Further Inequalities......Page 153
8.8 Exercises......Page 155
The Probabilistic Lens: Local Coloring......Page 156
9 Pseudorandomness......Page 159
9.1 The Quadratic Residue Tournaments......Page 160
9.2 Eigenvalues and Expanders......Page 163
9.3 Quasirandom Graphs......Page 169
9.4 Exercises......Page 176
The Probabilistic Lens: Random Walks......Page 177
PART II TOPICS......Page 179
10 Random Graphs......Page 181
10.1 Subgraphs......Page 182
10.2 Clique Number......Page 184
10.3 Chromatic Number......Page 186
10.4 Zero-One Laws......Page 187
10.5 Exercises......Page 195
The Probabilistic Lens: Counting Subgraphs......Page 197
11 The Erdös–Rényi Phase Transition......Page 199
11.1 An Overview......Page 200
11.2 Three Processes......Page 202
11.3 The Galton–Watson Branching Process......Page 203
11.4 Analysis of the Poisson Branching Process......Page 204
11.5 The Graph Branching Model......Page 206
11.6 The Graph and Poisson Processes Compared......Page 207
11.8 The Subcritical Regimes......Page 210
11.9 The Supercritical Regimes......Page 211
11.10 The Critical Window......Page 214
11.11 Analogies to Classical Percolation Theory......Page 217
11.12 Exercises......Page 221
The Probabilistic Lens: The Rich Get Richer......Page 223
12.1 Preliminaries......Page 225
12.2 Random Restrictions and Bounded-Depth Circuits......Page 227
12.3 More on Bounded-Depth Circuits......Page 231
12.4 Monotone Circuits......Page 234
12.5 Formulae......Page 237
12.6 Exercises......Page 238
The Probabilistic Lens: Maximal Antichains......Page 239
13.1 Basics......Page 241
13.2 Six Standard Deviations Suffice......Page 243
13.3 Linear and Hereditary Discrepancy......Page 246
13.4 Lower Bounds......Page 249
13.5 The Beck-Fiala Theorem......Page 251
13.6 Exercises......Page 252
The Probabilistic Lens: Unbalancing Lights......Page 254
14 Geometry......Page 257
14.1 The Greatest Angle Among Points in Euclidean Spaces......Page 258
14.2 Empty Triangles Determined by Points in the Plane......Page 259
14.3 Geometrical Realizations of Sign Matrices......Page 261
14.4 ε-Nets and VC-Dimensions of Range Spaces......Page 263
14.5 Dual Shatter Functions and Discrepancy......Page 268
14.6 Exercises......Page 271
The Probabilistic Lens: Efficient Packing......Page 272
15.1 Codes......Page 275
15.2 Liar Game......Page 278
15.3 Tenure Game......Page 280
15.4 Balancing Vector Game......Page 281
15.6 Half Liar Game......Page 284
15.7 Entropy......Page 286
15.8 Exercises......Page 291
The Probabilistic Lens: An Extremal Graph......Page 293
16.1 The Method of Conditional Probabilities......Page 295
16.2 d-Wise Independent Random Variables in Small Sample Spaces......Page 300
16.3 Exercises......Page 304
The Probabilistic Lens: Crossing Numbers, Incidences, Sums and Products......Page 305
17.1 Property Testing......Page 309
17.2 Testing Colorability......Page 310
17.3 Szemerédi's Regularity Lemma......Page 314
17.4 Testing Triangle-Freeness......Page 318
17.5 Characterizing the Testable Graph Properties......Page 320
17.6 Exercises......Page 322
The Probabilistic Lens: Turán Numbers and Dependent Random Choice......Page 323
A.1 Chernoff Bounds......Page 327
A.2 Lower Bounds......Page 335
A.3 Exercises......Page 340
The Probabilistic Lens: Triangle-Free Graphs Have Large Independence Numbers......Page 341
B.1 Papers......Page 343
B.2 Conjectures......Page 345
B.3 On Erdös......Page 346
B.4 Uncle Paul......Page 347
References......Page 351
Author Index......Page 365
Subject Index......Page 369