- Hardcover: 376 pages
- Publisher: Wiley-Interscience; 3 edition (August 11, 2008)
- Language: English
- ISBN-10: 0470170204
- ISBN-13: 978-0470170205
- Product Dimensions: 6.4 x 1 x 9.6 inches
- Shipping Weight: 1.4 pounds
- Average Customer Review: 7 customer reviews
- Amazon Best Sellers Rank: #1,749,266 in Books (See Top 100 in Books)
Enter your mobile number or email address below and we'll send you a link to download the free Kindle App. Then you can start reading Kindle books on your smartphone, tablet, or computer - no Kindle device required.
To get the free app, enter your mobile phone number.
The Probabilistic Method 3rd Edition
Use the Amazon App to scan ISBNs and compare prices.
Fulfillment by Amazon (FBA) is a service we offer sellers that lets them store their products in Amazon's fulfillment centers, and we directly pack, ship, and provide customer service for these products. Something we hope you'll especially enjoy: FBA items qualify for FREE Shipping and Amazon Prime.
If you're a seller, Fulfillment by Amazon can help you increase your sales. We invite you to learn more about Fulfillment by Amazon .
There is a newer edition of this item:
Customers who viewed this item also viewed
Customers who bought this item also bought
From the Back Cover
Praise for the Second Edition:
"Serious researchers in combinatorics or algorithm design will wish to read the book in its entirety...the book may also be enjoyed on a lighter level since the different chapters are largely independent and so it is possible to pick out gems in one's own area..."
—Formal Aspects of Computing
This Third Edition of The Probabilistic Method reflects the most recent developments in the field while maintaining the standard of excellence that established this book as the leading reference on probabilistic methods in combinatorics. Maintaining its clear writing style, illustrative examples, and practical exercises, this new edition emphasizes methodology, enabling readers to use probabilistic techniques for solving problems in such fields as theoretical computer science, mathematics, and statistical physics.
The book begins with a description of tools applied in probabilistic arguments, including basic techniques that use expectation and variance as well as the more recent applications of martingales and correlation inequalities. Next, the authors examine where probabilistic techniques have been applied successfully, exploring such topics as discrepancy and random graphs, circuit complexity, computational geometry, and derandomization of randomized algorithms. Sections labeled "The Probabilistic Lens" offer additional insights into the application of the probabilistic approach, and the appendix has been updated to include methodologies for finding lower bounds for Large Deviations.
The Third Edition also features:
A new chapter on graph property testing, which is a current topic that incorporates combinatorial, probabilistic, and algorithmic techniques
An elementary approach using probabilistic techniques to the powerful Szemerédi Regularity Lemma and its applications
New sections devoted to percolation and liar games
A new chapter that provides a modern treatment of the Erdös-Rényi phase transition in the Random Graph Process
Written by two leading authorities in the field, The Probabilistic Method, Third Edition is an ideal reference for researchers in combinatorics and algorithm design who would like to better understand the use of probabilistic methods. The book's numerous exercises and examples also make it an excellent textbook for graduate-level courses in mathematics and computer science.
About the Author
NOGA ALON, PhD, is Baumritter Professor of Mathematics and Computer Science at Tel Aviv University, Israel. A member of the Israel National Academy of Sciences, Dr. Alon has written over 400 published papers, mostly in the areas of combinatorics and theoretical computer science. He is the recipient of numerous honors in the field, including the Erdös Prize (1989), the Pólya Prize (2000), the Landau Prize (2005), and the Gödel Prize (2005).
JOEL H. SPENCER, PhD, is Professor of Mathematics and Computer Science at the Courant Institute of Mathematical Sciences at New York University and is the cofounder and coeditor of the journal Random Structures and Algorithms. Dr. Spencer has written over 150 published articles and is the coauthor of Ramsey Theory, Second Edition, also published by Wiley.
Showing 1-7 of 7 reviews
There was a problem filtering reviews right now. Please try again later.
The introduction and breadth of examples and applied topics are wonderful. I particularly enjoyed their treatments of the local lemma, circuit complexity, and graph property testing. In addition, between each chapter there is an example of an elegant use of the probabilistic method (usually the techniques displayed from the previous chapter) which they collectively call "The probabilistic Lens." These proofs are definitely worth reading, but not necessary to understand the rest of the text.
That being said, there were some parts of this book that I thought fell short. In particular, many of the applications in the topics chapters begin with the most complicated examples, and either omit or downplay the historically first and technically simpler results. For instance, in the chapter on graph property testing they discuss colorability and not connectivity. In their treatment on the ER-phase transition for random graphs, they jump immediately into "fine parameterizations" of the model, and it comes together in a kludgy way, making the analysis much more detailed and complicated than it needs to be. The connection between the big picture and these details was too tenuous for comfort. Instead of this book, I would recommend referring to Bela Bollobas's Random Graphs (Cambridge Studies in Advanced Mathematics), which gives a much more fluid treatment of these topics.
My last objection is the authors' dismissive use of the Chernoff bounds. I understand that a serious reader of this text should be well versed in Chernoff bounds, but their treatment (and somewhat messy appendix covering the basics) does not explain clearly enough how to apply these crucial bounds to problems when it's not obvious they apply. Considering how frequently the Chernoff bounds are used in practice, considering how they introduce other elementary topics like the second moment, and considering that this book is about applications (and uses Chernoff heavily), I would have liked to see an entire chapter dedicated to its use, perhaps between the second moment and the Local Lemma chapters.
The content is well written and organized.
The proof detail of theorem is very reasonable. May omit something, but for the reader have some math background, it is quite easy to complete the proofs.
5 star without thinking.
The mathematical prerequisites are not very high, but some knowledge of probability theory ( not the measure - theoretic stuff, however, as virtually everything is countable.) and of graph theory (as many examples and trheorems refer to graphs and their properties), maybe at the level of Bolodas' Modern Graph Theory is definitely helpful.
The proofs are generally not too difficult ( I am only a "hobby mathematician", this may help to evaluate the statement), and very often they are truly "surprising"!
The book contains very few typos ( I counted around 20 only ), and most of them are harmless.
I recommend this book to anybody interested in discrete mathematics, or interested in beautiful proofs.
The Kindle version is a trash. Since Amazon transfered many formulas by plane alphabets in a hapharzard manner , I can find at least one typo in each page. The authors could feel insulted by this.