This is the third edition of the book; it contains several improved results and covers various additional topics that developed extensively during the last few years. The additions include a modem treatment of the Erdos-Renyi phase transition discussed in Chapter 11, focusing on the behavior of the random graph near the emergence of the giant component and briefly exploring its connection to classical percolation theory. Another addition is Chapter 17, Graph Property Testing—a recent topic that combines combinatorial, probabilistic and algorithmic techniques. This chapter also includes a proof of the Regularity Lemma of Szemeredi (described in a probabilistic language) and a presentation of some of its applications in the area. Further additions are two new Probabilistic Lenses, several additional exercises, and a new part in Appendix A focused on lower bounds.
Author(s): Noga Alon, Joel H. Spencer
Series: Wiley-Interscience Series in Discrete Mathematics and Optimization
Edition: 3
Publisher: Wiley
Year: 2008
Language: English
Pages: 371
Tags: Математика;Дискретная математика;
Alon N,Spencer J.H. The Probabilistic Method(3rd ed., Wiley,2008)(ISBN 9780470170205)(600 dpi)(371p) ......Page 4
Copyright ......Page 5
Contents vii ......Page 7
PREFACE xiii ......Page 13
ACKNOWLEDGMENTS xv ......Page 15
PART I METHODS xvi ......Page 16
1.1 The Probabilistic Method 1 ......Page 17
1.2 Graph Theory 3 ......Page 19
1.3 Combinatorics 7 ......Page 23
1.4 Combinatorial Number Theory 9 ......Page 25
1.5 Disjoint Pairs 10 ......Page 26
1.6 Exercises 11 ......Page 27
The Probabilistic Lens: The Erdds-Ko-Rado Theorem 13 ......Page 29
2.1 Basics 15 ......Page 31
2.2 Splitting Graphs 16 ......Page 32
2.3 Two Quickies 18 ......Page 34
2.4 Balancing Vectors 19 ......Page 35
2.5 Unbalancing Lights 21 ......Page 37
2.6 Without Coin Flips 22 ......Page 38
2.7 Exercises 23 ......Page 39
The Probabilistic Lens: Bregman s Theorem 24 ......Page 40
3.1 Ramsey Numbers 27 ......Page 43
3.2 Independent Sets 29 ......Page 45
3.3 Combinatorial Geometry 30 ......Page 46
3.4 Packing 31 ......Page 47
3.5 Recoloring 32 ......Page 48
3.6 Continuous Time 35 ......Page 51
3.7 Exercises 39 ......Page 55
The Probabilistic Lens: High Girth and High Chromatic Number 41 ......Page 57
4.1 Basics 43 ......Page 59
4.2 Number Theory 44 ......Page 60
4.3 More Basics 47 ......Page 63
4.4 Random Graphs 49 ......Page 65
4.5 Clique Number 53 ......Page 69
4.6 Distinct Sums 54 ......Page 70
4.7 The Rodl Nibble 56 ......Page 72
4.8 Exercises 61 ......Page 77
The Probabilistic Lens: Hamiltonian Paths 63 ......Page 79
5.1 The Lemma 67 ......Page 83
5.2 Property B and Multicolored Sets of Real Numbers 70 ......Page 86
5.3 Lower Bounds for Ramsey Numbers 71 ......Page 87
5.4 A Geometric Result 73 ......Page 89
5.5 The Linear Arboricity of Graphs 74 ......Page 90
5.6 Latin Transversals 78 ......Page 94
5.7 The Algorithmic Aspect 79 ......Page 95
5.8 Exercises 82 ......Page 98
The Probabilistic Lens: Directed Cycles 83 ......Page 99
6 Correlation Inequalities 85 ......Page 101
6.1 The Four Functions Theorem of Ahlswede and Daykin 86 ......Page 102
6.2 The FKG Inequality 89 ......Page 105
6.3 Monotone Properties 90 ......Page 106
6.4 Linear Extensions of Partially Ordered Sets 92 ......Page 108
6.5 Exercises 94 ......Page 110
The Probabilistic Lens: Turan s Theorem 95 ......Page 111
7.1 Definitions 97 ......Page 113
7.2 Large Deviations 99 ......Page 115
7.3 Chromatic Number 101 ......Page 117
7.4 Two General Settings 103 ......Page 119
7.5 Four Illustrations 107 ......Page 123
7.6 Talagrand’s Inequality 109 ......Page 125
7.7 Applications of Talagrand’s Inequality 113 ......Page 129
7.8 Kim-Vu Polynomial Concentration 115 ......Page 131
7.9 Exercises 116 ......Page 132
The Probabilistic Lens: Weierstrass Approximation Theorem 117 ......Page 133
8.1 The Janson Inequalities 119 ......Page 135
8.2 The Proofs 121 ......Page 137
8.3 Brun’s Sieve 124 ......Page 140
8.4 Large Deviations 127 ......Page 143
8.5 Counting Extensions 129 ......Page 145
8.6 Counting Representations 130 ......Page 146
8.7 Further Inequalities 133 ......Page 149
8.8 Exercises 135 ......Page 151
The Probabilistic Lens: Local Coloring 136 ......Page 152
9 Pseudorandomness 139 ......Page 155
9.1 The Quadratic Residue Tournaments 140 ......Page 156
9.2 Eigenvalues and Expanders 143 ......Page 159
9.3 Quasirandom Graphs 149 ......Page 165
9.4 Exercises 156 ......Page 172
The Probabilistic Lens: Random Walks 157 ......Page 173
PART II TOPICS 160 ......Page 175
10 Random Graphs 161 ......Page 177
10.1 Subgraphs 162 ......Page 178
10.2 Clique Number 164 ......Page 180
10.3 Chromatic Number 166 ......Page 182
10.4 Zero-One Laws 167 ......Page 183
10.5 Exercises 175 ......Page 191
The Probabilistic Lens: Counting Subgraphs 177 ......Page 193
11 The Erdos-Renyi Phase Transition 179 ......Page 195
11.1 An Overview 180 ......Page 196
11.2 Three Processes 182 ......Page 198
11.3 The Galton-Watson Branching Process 183 ......Page 199
11.4 Analysis of the Poisson Branching Process 184 ......Page 200
11.5 The Graph Branching Model 186 ......Page 202
11.6 The Graph and Poisson Processes Compared 187 ......Page 203
11.8 The Subcritical Regimes 190 ......Page 206
11.9 The Supercritical Regimes 191 ......Page 207
11.10 The Critical Window 194 ......Page 210
11.11 Analogies to Classical Percolation Theory 197 ......Page 213
11.12 Exercises 201 ......Page 217
The Probabilistic Lens: The Rich Get Richer 203 ......Page 219
12.1 Preliminaries 205 ......Page 221
12.2 Random Restrictions and Bounded-Depth Circuits 207 ......Page 223
12.3 More on Bounded-Depth Circuits 211 ......Page 227
12.4 Monotone Circuits 214 ......Page 230
12.5 Formulae 217 ......Page 233
12.6 Exercises 218 ......Page 234
The Probabilistic Lens: Maximal Antichains 219 ......Page 235
13.1 Basics 221 ......Page 237
13.2 Six Standard Deviations Suffice 223 ......Page 239
13.3 Linear and Hereditary Discrepancy 226 ......Page 242
13.4 Lower Bounds 229 ......Page 245
13.5 The Beck-Fiala Theorem 231 ......Page 247
13.6 Exercises 232 ......Page 248
The Probabilistic Lens: Unbalancing Lights 234 ......Page 250
14 Geometry 237 ......Page 253
14.1 The Greatest Angle Among Points in Euclidean Spaces 238 ......Page 254
14.2 Empty Triangles Determined by Points in the Plane 239 ......Page 255
14.3 Geometrical Realizations of Sign Matrices 241 ......Page 257
14.4 e-Nets and VC-Dimensions of Range Spaces 243 ......Page 259
14.5 Dual Shatter Functions and Discrepancy 248 ......Page 264
14.6 Exercises 251 ......Page 267
The Probabilistic Lens: Efficient Packing 252 ......Page 268
15.1 Codes 255 ......Page 271
15.2 Liar Game 258 ......Page 274
15.3 Tenure Game 260 ......Page 276
15.4 Balancing Vector Game 261 ......Page 277
15.6 Half Liar Game 264 ......Page 280
15.7 Entropy 266 ......Page 282
15.8 Exercises 271 ......Page 287
The Probabilistic Lens: An Extremal Graph 273 ......Page 289
16.1 The Method of Conditional Probabilities 275 ......Page 291
16.2 d-Wise Independent Random Variables in Small Sample Spaces 280 ......Page 296
16.3 Exercises 284 ......Page 300
The Probabilistic Lens: Crossing Numbers, Incidences, Sums and Products 285 ......Page 301
17.1 Property Testing 289 ......Page 305
17.2 Testing Colorability 290 ......Page 306
17.3 Szemeredi’s Regularity Lemma 294 ......Page 310
17.4 Testing Triangle-Freeness 298 ......Page 314
17.5 Characterizing the Testable Graph Properties 300 ......Page 316
17.6 Exercises 302 ......Page 318
The Probabilistic Lens: Turan Numbers and Dependent Random Choice 303 ......Page 319
A.l Chemoff Bounds 307 ......Page 323
A.2 Lower Bounds 315 ......Page 331
A.3 Exercises 320 ......Page 336
The Probabilistic Lens: Triangle-Free Graphs Have Large Independence Numbers 321 ......Page 337
B.l Papers 323 ......Page 339
B.2 Conjectures 325 ......Page 341
B.3 On Erdos 326 ......Page 342
B.4 Uncle Paul 327 ......Page 343
References 331 ......Page 347
Author Index 345 ......Page 361
Subject Index 349 ......Page 365
cover......Page 1
