Ten Lectures on the Probabilistic Method: Second EditionThis update of the 1987 title of the same name is an examination of what is currently known about the probabilistic method, written by one of its principal developers. Based on the notes from Spencer's 1986 series of ten lectures, this new edition contains an additional lecture: The Janson Inequalities. These inequalities allow accurate approximation of extremely small probabilities. A new algorithmic approach to the Lovasz Local Lemma, attributed to Jozsef Beck, has been added to Lecture 8, as well. |
Contents
CB64_ch1 | 1 |
CB64_ch2 | 11 |
CB64_ch3 | 17 |
CB64_ch4 | 29 |
CB64_ch5 | 37 |
CB64_ch6 | 45 |
CB64_ch7 | 51 |
CB64_ch8 | 57 |
CB64_ch9 | 67 |
CB64_ch10 | 75 |
CB64_ch11 | 81 |
87 | |
Other editions - View all
Common terms and phrases
adjacent algorithm apply asymptotic b₁ Beck-Fiala Theorem Blue calculation chips chromatic number combinatorial components constant define deg A)≤t dependency graph disc discrepancy distribution edges event exists expected number fixed floating given gives graph G Hamiltonian path Hence herdisc indicator random variable integer intersect iterate Janson Inequality JOEL SPENCER Jozsef Beck k-coloring least Let A₁ lim Pr lindisc linearity of expectation Lovász Local Lemma lower bound martingale Math Mathematical matrix maximal monochromatic mutually independent n-sets nonupsets p₁ Paul Erdös Pigeonhole Principle players points Poisson polynomial Pr Ă Pr TF probabilistic method probability space problem Proof Ramsey function Ramsey's Theorem random graph random variable randomly ranking result S₁ Saharon Shelah second moment method SPENCER switches Theory threshold function tournament two-coloring u₁ uncolored upper bound vectors vertices W₁ x₁ y₁ zero Zero-One Law Σ Σ