Die hier beschriebene Erdos-Wahrscheinlichkeitsmethode erlaubt den
Beweis der Existenz einer kombinatorischen Struktur mit bestimmen
Eigenschaften. Dazu wird ein geeigneter Wahrscheinlichkeitsraum
konstruiert und gezeigt, daß ein zufällig ausgewähltes Element
dieses Raumes die gewünschten Eigenschaften mit positiver
Wahrscheinlichkeit aufweist. - Diese 2. überarbeitete Auflage wird
mit Sicherheit zum Standard-Nachschlagewerk der
Wahrscheinlichkeitsmethoden in der Kombinatorik! (11/00)
This book is the leading reference on probabilistic methods in
combinatorics, and there is no direct competition. The
Probabilistic Method, Third Edition begins with basic techniques
that use expectation and variance, as well as the more recent
martingales and correlation inequalities, then explores areas where
probabilistic techniques proved successful, including discrepancy
and random graphs as well as cutting-edge topics in theoretical
computer science. A series of proofs, or "probabilistic
lenses," are interspersed throughout the book, offering added
insight into the application of the probabilistic approach. The
number of exercises included in the third edition has been almost
doubled from that of the second edition, and hints and/or answers
to some of the exercises are provided.
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.
Inhaltsangabe
- Dedication - Preface - Acknowledgments
Part I. METHODS 1. The Basic Method - The Probabilistic Lens: The Erd" osKoRado Theorem 2. Linearity of Expectation - The Probabilistic Lens: Brégman's Theorem 3. Alterations - The Probabilistic Lens: High Girth and High Chromatic Number 4. The Second Moment - The Probabilistic Lens: Hamiltonian Paths 5. The Local Lemma - The Probabilistic Lens: Directed Cycles 6. Correlation Inequalities - and Daykin - The Probabilistic Lens: Turán's Theorem 7. Martingales and Tight Concentration - The Probabilistic Lens: Weierstrass Approximation Theorem 8. The Poisson Paradigm - The Probabilistic Lens: Local Coloring 9. Pseudorandomness - The Probabilistic Lens: Random Walks
Part II. TOPICS 10. Random Graphs - The Probabilistic Lens: Counting Subgraphs 11. The Erd" osR - 'enyi Phase Transition - The Probabilistic Lens: The Rich Get Richer 12. Circuit Complexity - The Probabilistic Lens: Maximal Antichains 13. Discrepancy - The Probabilistic Lens: Unbalancing Lights 14. Geometry - The Probabilistic Lens: Efficient Packing 15. Codes, Games and Entropy - The Probabilistic Lens: An Extremal Graph 16. Derandomization - The Probabilistic Lens: Crossing Numbers, Incidences, Sums and Products 17. Graph Property Testing - The Probabilistic Lens: Tur?an Numbers and Dependent Random Choice - Appendix A: Bounding of Large Deviations - The Probabilistic Lens: Trianglefree Graphs Have Large Independence Numbers
- Appendix B: Paul Erd" os - References - Subject Index - Author Index
