Ten Lectures on the Probabilistic Method: Second Edition
This 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.
What people are saying - Write a review
We haven't found any reviews in the usual places.
LECTURE 1 The Probabilistic Method
LECTURE 2 The Deletion Method and Other Refinements
LECTURES Random Graphs I
LECTURE 4 Large Deviations and Nonprobabilistic Algorithms
LECTURE 5 Discrepancy I
LECTURE 6 Chaos from Order
LECTURE 7 Random Graphs II
addends adjacent algorithm apply arbitrary argument asymptotic Beck-Fiala Theorem Blue calculation chips chromatic number combinatorial components constant define denote dependency graph disc discrepancy event example exists expected number fc-coloring fc-set finite set fixed given gives graph G graph theory Hamiltonian path Hence herdisc incidence matrix indicator random variable integer intersect iterate JOEL SPENCER Jozsef Beck least let G lindisc linearity of expectation Lovasz Local Lemma lower bound martingale Math Mathematical matrix maximal monochromatic mutually independent n-sets Noga Alon nonupsets Paul Erdos perfect partial coloring Permutation Pigeonhole Principle players Poisson polynomial positive probability Pr[A Pr[X precisely probabilistic method probability space problem Proof Ramsey function Ramsey's Theorem random graph randomly result roughly Saharon Shelah second moment method SPENCER Theory threshold function two-coloring upper bound vectors vertex vertices W°LD zero Zero-One Law