Table of Contents 1 Preliminaries 6 1.1 Probability Theory..........................6 1.2 Useful Estimates 9 2 The Probabilistic Method 11 2.1 Ramsey Numbers.... 11 2.2 Hypergraph Coloring. 2.3 The Erdos-Ko-Rado Theorem.......... 15 2.4 Pairs of Sets... 16 3 Linearity of Expectation 18 3.1 Computing Expectation Using Indicators............. 18 3.2 Hamiltonian Paths........................l9 3.3 Splitting Graphs 。。。 4 Alterations 21 4.1 Independent Sets 4.2 High Girth and High Chromatic Number.............22 5 The Second Mo ent 24 . Variance and the Chebyshev Inequality 5.2 Estimating the Middle Binomial Coefficient··,,,··,·,,·25 5.3 Threshold Functions...·...··.·.:······。····· 26 5.4 The Clique Number......................,.. 29 6 The Lovasz Local Lemma 33 0.1 Statement and Proof 33 6.2 ypergraph Coloring Again···...··.·...·.··..··36 6.3 Directed Cycles,...,...,......,,,.,,..,.., 36 6.4 Ridiculous Iniections......................... 37 6.5 Coloring of Real Numbers...................... 7 Strong Concentration Around the Expectation 7.1 Sum of Independent Uniform+1 Variables. 7.2 Sums of Bounded Independent Random Variables.,··,··.. 42 7.3 A Lower Bound For the Binomial Distribution····.·.···45 7.4 Sums of Moderately Dependent Indicator Variables........48Table of Contents 1 Preliminaries 6 1.1 Probability Theory . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.2 Useful Estimates . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2 The Probabilistic Method 11 2.1 Ramsey Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Hypergraph Coloring . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.3 The Erd˝os–Ko–Rado Theorem . . . . . . . . . . . . . . . . . . . 15 2.4 Pairs of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3 Linearity of Expectation 18 3.1 Computing Expectation Using Indicators . . . . . . . . . . . . . 18 3.2 Hamiltonian Paths . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.3 Splitting Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4 Alterations 21 4.1 Independent Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.2 High Girth and High Chromatic Number . . . . . . . . . . . . . 22 5 The Second Moment 24 5.1 Variance and the Chebyshev Inequality . . . . . . . . . . . . . . 24 5.2 Estimating the Middle Binomial Coefficient . . . . . . . . . . . . 25 5.3 Threshold Functions . . . . . . . . . . . . . . . . . . . . . . . . . 26 5.4 The Clique Number . . . . . . . . . . . . . . . . . . . . . . . . . 29 6 The Lovász Local Lemma 33 6.1 Statement and Proof . . . . . . . . . . . . . . . . . . . . . . . . . 33 6.2 Hypergraph Coloring Again . . . . . . . . . . . . . . . . . . . . . 36 6.3 Directed Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.4 Ridiculous Injections . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.5 Coloring of Real Numbers . . . . . . . . . . . . . . . . . . . . . . 38 7 Strong Concentration Around the Expectation 40 7.1 Sum of Independent Uniform ±1 Variables . . . . . . . . . . . . . 41 7.2 Sums of Bounded Independent Random Variables . . . . . . . . . 42 7.3 A Lower Bound For the Binomial Distribution . . . . . . . . . . 45 7.4 Sums of Moderately Dependent Indicator Variables . . . . . . . . 48