i进 CONTENTS 2.5 Unbalancing Lights.25 2.6 Without Coin Flips,26 2.7 Exercises.27 Brigman's Theorem,29 3 Alterations 31 3.1 Ramsey Numbers,31 ndent Sets,33 33 ial Geometry,34 5 Packing. Greedy Coloring.36 6 Continuous Time,38 3.7 Exercises.41 High Girth and High Chromatic Number,43 4 The Second Moment 45 4.1 Basics,45 40 Number Theory,46 43 More Basics .49 44 Random Grap 4.5 que Numb Dis 57 The Rodl nib ble,58 4.8 Exercises,64 Hamiltonian Paths,65 5 The Local Lemma 5.1 The lemma 69 5.2 Property B and Multicolored Sets of Real Numbers,72 5.3 Bou nds for Ran 54 The Linear Arb 5.6 of Graphs.76 atin Iransversals,8 5.7 Moser's Fix-It Algorithm,81 5.8 Exercises.87 Directed Cycles,88 6 Correlation Inequalities 89 6.1 The Four Functions Theorem of Ahlswede and Daykin,90 6.2 The FKG Inequality,93 6.3 Monotone Properties,94 viii CONTENTS 2.5 Unbalancing Lights, 25 2.6 Without Coin Flips, 26 2.7 Exercises, 27 Brégman’s Theorem, 29 3 Alterations 31 3.1 Ramsey Numbers, 31 3.2 Independent Sets, 33 3.3 Combinatorial Geometry, 34 3.4 Packing, 35 3.5 Greedy Coloring, 36 3.6 Continuous Time, 38 3.7 Exercises, 41 High Girth and High Chromatic Number, 43 4 The Second Moment 45 4.1 Basics, 45 4.2 Number Theory, 46 4.3 More Basics, 49 4.4 Random Graphs, 51 4.5 Clique Number, 55 4.6 Distinct Sums, 57 4.7 The Rödl nibble, 58 4.8 Exercises, 64 Hamiltonian Paths, 65 5 The Local Lemma 69 5.1 The Lemma, 69 5.2 Property B and Multicolored Sets of Real Numbers, 72 5.3 Lower Bounds for Ramsey Numbers, 73 5.4 A Geometric Result, 75 5.5 The Linear Arboricity of Graphs, 76 5.6 Latin Transversals, 80 5.7 Moser’s Fix-It Algorithm, 81 5.8 Exercises, 87 Directed Cycles, 88 6 Correlation Inequalities 89 6.1 The Four Functions Theorem of Ahlswede and Daykin, 90 6.2 The FKG Inequality, 93 6.3 Monotone Properties, 94