Probabilistic Method

Noga Alon, PhD, is Baumritter Professor of Mathematics and Computer Science at Tel Aviv University. He is a member of the Israel National Academy of Sciences and Academia Europaea. A coeditor of the journal Random Structures and Algorithms, Dr. Alon is the recipient of the Polya Prize, The Gödel Prize, The Israel Prize, and the EMET Prize.Joel H. Spencer, PhD, is Professor of Mathematics and Computer Science at the Courant Institute of New York University. He is the cofounder and coeditor of the journal Random Structures and Algorithms and is a Sloane Foundation Fellow. Dr. Spencer has written more than 200 published articles and is the coauthor of Ramsey Theory, Second Edition, also published by Wiley.

• PREFACE xiiiACKNOWLEDGMENTS xvPART I METHODS 11 The Basic Method 31.1 The Probabilistic Method, 31.2 Graph Theory, 51.3 Combinatorics, 91.4 Combinatorial Number Theory, 111.5 Disjoint Pairs, 121.6 Independent Sets and List Coloring, 131.7 Exercises, 16The Erd˝os–Ko–Rado Theorem, 182 Linearity of Expectation 192.1 Basics, 192.2 Splitting Graphs, 202.3 Two Quickies, 222.4 Balancing Vectors, 232.5 Unbalancing Lights, 252.6 Without Coin Flips, 262.7 Exercises, 27Brégman’s Theorem, 293 Alterations 313.1 Ramsey Numbers, 313.2 Independent Sets, 333.3 Combinatorial Geometry, 343.4 Packing, 353.5 Greedy Coloring, 363.6 Continuous Time, 383.7 Exercises, 41High Girth and High Chromatic Number, 434 The Second Moment 454.1 Basics, 454.2 Number Theory, 464.3 More Basics, 494.4 Random Graphs, 514.5 Clique Number, 554.6 Distinct Sums, 574.7 The Rödl nibble, 584.8 Exercises, 64Hamiltonian Paths, 655 The Local Lemma 695.1 The Lemma, 695.2 Property B and Multicolored Sets of Real Numbers, 725.3 Lower Bounds for Ramsey Numbers, 735.4 A Geometric Result, 755.5 The Linear Arboricity of Graphs, 765.6 Latin Transversals, 805.7 Moser’s Fix-It Algorithm, 815.8 Exercises, 87Directed Cycles, 886 Correlation Inequalities 896.1 The Four Functions Theorem of Ahlswede and Daykin, 906.2 The FKG Inequality, 936.3 Monotone Properties, 946.4 Linear Extensions of Partially Ordered Sets, 976.5 Exercises, 99Turán’s Theorem, 1007 Martingales and Tight Concentration 1037.1 Definitions, 1037.2 Large Deviations, 1057.3 Chromatic Number, 1077.4 Two General Settings, 1097.5 Four Illustrations, 1137.6 Talagrand’s Inequality, 1167.7 Applications of Talagrand’s Inequality, 1197.8 Kim–Vu Polynomial Concentration, 1217.9 Exercises, 123Weierstrass Approximation Theorem, 1248 The Poisson Paradigm 1278.1 The Janson Inequalities, 1278.2 The Proofs, 1298.3 Brun’s Sieve, 1328.4 Large Deviations, 1358.5 Counting Extensions, 1378.6 Counting Representations, 1398.7 Further Inequalities, 1428.8 Exercises, 143Local Coloring, 1449 Quasirandomness 1479.1 The Quadratic Residue Tournaments, 1489.2 Eigenvalues and Expanders, 1519.3 Quasirandom Graphs, 1579.4 Szemerédi’s Regularity Lemma, 1659.5 Graphons, 1709.6 Exercises, 172Random Walks, 174PART II TOPICS 17710 Random Graphs 17910.1 Subgraphs, 18010.2 Clique Number, 18310.3 Chromatic Number, 18410.4 Zero–One Laws, 18610.5 Exercises, 193Counting Subgraphs, 19511 The Erd˝os–Rényi Phase Transition 19711.1 An Overview, 19711.2 Three Processes, 19911.3 The Galton–Watson Branching Process, 20111.4 Analysis of the Poisson Branching Process, 20211.5 The Graph Branching Model, 20411.6 The Graph and Poisson Processes Compared, 20511.7 The Parametrization Explained, 20711.8 The Subcritical Regions, 20811.9 The Supercritical Regimes, 20911.10 The Critical Window, 21211.11 Analogies to Classical Percolation Theory, 21411.12 Exercises, 219Long paths in the supercritical regime, 22012 Circuit Complexity 22312.1 Preliminaries, 22312.2 Random Restrictions and Bounded-Depth Circuits, 22512.3 More on Bounded-Depth Circuits, 22912.4 Monotone Circuits, 23212.5 Formulae, 23512.6 Exercises, 236Maximal Antichains, 23713 Discrepancy 23913.1 Basics, 23913.2 Six Standard Deviations Suffice, 24113.3 Linear and Hereditary Discrepancy, 24513.4 Lower Bounds, 24813.5 The Beck–Fiala Theorem, 25013.6 Exercises, 251Unbalancing Lights, 25314 Geometry 25514.1 The Greatest Angle Among Points in Euclidean Spaces, 25614.2 Empty Triangles Determined by Points in the Plane, 25714.3 Geometrical Realizations of Sign Matrices, 25914.4 𝜖-Nets and VC-Dimensions of Range Spaces, 26114.5 Dual Shatter Functions and Discrepancy, 26614.6 Exercises, 269Efficient Packing, 27015 Codes, Games, and Entropy 27315.1 Codes, 27315.2 Liar Game, 27615.3 Tenure Game, 27815.4 Balancing Vector Game, 27915.5 Nonadaptive Algorithms, 28115.6 Half Liar Game, 28215.7 Entropy, 28415.8 Exercises, 289An Extremal Graph, 29116 Derandomization 29316.1 The Method of Conditional Probabilities, 29316.2 d-Wise Independent Random Variables in Small Sample Spaces, 29716.3 Exercises, 302Crossing Numbers, Incidences, Sums and Products, 30317 Graph Property Testing 30717.1 Property Testing, 30717.2 Testing Colorability, 30817.3 Testing Triangle-Freeness, 31217.4 Characterizing the Testable Graph Properties, 31417.5 Exercises, 316Turán Numbers and Dependent Random Choice, 317Appendix A Bounding of Large Deviations 321A.1 Chernoff Bounds, 321A.2 Lower Bounds, 330A.3 Exercises, 334Triangle-Free Graphs Have Large Independence Numbers, 336Appendix B Paul Erd˝os 339B.1 Papers, 339B.2 Conjectures, 341B.3 On Erd˝os, 342B.4 Uncle Paul, 343The Rich Get Richer, 346Appendix C Hints to Selected Exercises 349REFERENCES 355AUTHOR INDEX 367SUBJECT INDEX 371

"This is an ideal textbook for upper-undergraduate and graduate-level students majoring in mathematics, computer science, operations research, and statistics." (Springer Nature, 2016)