SIAM Homepage | Search Catalog | New Books | Author Index | Series Index | Title Index | View My Shopping Cart



The catalog and shopping cart are hosted for SIAM by EasyCart. Your transaction is secure. If you have any questions about your order, contact siambooks@siam.org.

Purchase Now!

Ten Lectures on the Probabilistic Method, Second EditionTen Lectures on the Probabilistic Method, Second Edition

Joel Spencer



CBMS-NSF Regional Conference Series in Applied Mathematics 64

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.

Throughout the monograph, Spencer retains the informal style of his original lecture notes and emphasizes the methodology, shunning the more technical "best possible" results in favor of clearer exposition. The book is not encyclopedic--it contains only those examples that clearly display the methodology.

The probabilistic method is a powerful tool in graph theory, combinatorics, and theoretical computer science. It allows one to prove the existence of objects with certain properties (e.g., colorings) by showing that an appropriately defined random object has positive probability of having those properties.

Audience

Geared toward faculty and students in discrete mathematics and computer science, this monograph is ideal for use in a seminar. The only necessary background is a basic undergraduate course in probability or discrete mathematics.

Contents

The Probabilistic Method; The Deletion Method and Other Refinements; Random Graphs I; Large Deviations and Nonprobabilistic Algorithms; Discrepancy I; Chaos from Order; Random Graphs II; The Lovasz Local Lemma; Discrepancy II; Six Standard Deviations Suffice; The Janson Inequalities.

1993 / x + 88 pages / Softcover / ISBN-13: 978-0-898713-25-1 / ISBN-10: 0-89871-325-0 /
List Price $44.50 / SIAM/CBMS Member Price $31.15 / Order Code CB64
Price
Quantity desired
   



Search our catalog for:

Shopping cart provided by: EasyCart.com
Select quantity and list or member price and then click the "Click to Order" button to add books to your shopping cart.
Banner art adapted from a figure by Hinke M. Osinga and Bernd Krauskopf (University of Auckland, NZ.)