The Probabilistic Method, 3rd Edition

by Noga Alon (Tel Aviv Univ., Israel); Joel H. Spencer (New York Univ. )

• ISBN13: 9780470277317
• ISBN10: 0470277319
• Format: eBook
• Copyright: 2008-05-01
• Publisher: Wiley-Interscience

Summary

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 Szemeredi Regularity Lemma and its applications New sections devoted to percolation and liar games A new chapter that provides a modern treatment of the Erdos-Renyi 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.

Table of Contents

Dedication

Preface

Acknowledgments

PART IMETHODS.

The Basic Method.

The Probabilistic Method

Graph Theory

Combinatorics

Combinatorial Number Theory

Disjoint Pairs

Exercises

The Probabilistic Lens: The Erd" osKoRado Theorem

Linearity of Expectation.

Basics

Splitting Graphs

Two Quickies

Balancing Vectors

Unbalancing Lights

Without Coin Flips

Exercises

The Probabilistic Lens: BrégmanÆs Theorem

Alterations.

Ramsey Numbers

Independent Sets

Combinatorial Geometry

Packing

Recoloring

Continuous Time

Exercises

The Probabilistic Lens: High Girth and High Chromatic Number

The Second Moment.

Basics

Number Theory

More Basics

Random Graphs

Clique Number

Distinct Sums

The Rödl Nibble

Exercises

The Probabilistic Lens: Hamiltonian Paths

The Local Lemma.

The Lemma

Property B and Multicolored Sets of Real Numbers

Lower Bounds for Ramsey Numbers

A Geometric Result

The Linear Arboricity of Graphs

Latin Transversals

The Algorithmic Aspect

Exercises

The Probabilistic Lens: Directed Cycles

Correlation Inequalities.

The Four Functions Theorem of Ahlswede and Daykin

The FKG Inequality

Monotone Properties

Linear Extensions of Partially Ordered Sets

Exercises

The Probabilistic Lens: TuránÆs Theorem

Martingales and Tight Concentration.

Definitions

Large Deviations

Chromatic Number

Two General Settings

Four Illustrations

TalagrandÆs Inequality

Applications of TalagrandÆs Inequality

KimVu

Exercises

The Probabilistic Lens: Weierstrass Approximation Theorem

The Poisson Paradigm.

The Janson Inequalities

The Proofs

BrunÆs Sieve

Large Deviations

Counting Extensions

Counting Representations

Further Inequalities

Exercises

The Probabilistic Lens: Local Coloring

Pseudorandomness.

The Quadratic Residue Tournaments

Eigenvalues and Expanders

Quasi Random Graphs

Exercises

The Probabilistic Lens: Random Walks

Topics.

Random Graphs

Subgraphs

Clique Number

Chromatic Number

ZeroOne Laws

Exercises

The Probabilistic Lens: Counting Subgraphs

The Erd" osRÆenyi Phase Transition

An Overview

Three Processes

The GaltonWatson Branching Process

Analysis of the Poisson Branching Process

The Graph Branching Model

The Graph and Poisson Processes Compared

The Parametrization Explained

The Subcritical Regions

The Supercritical Regimes

The Critical Window

Analogies to Classical Percolation Theory

Exercises

The Probabilistic Lens: The Rich Get Richer

Circuit Complexity.

Preliminaries 318

Random Restrictions and BoundedDepth Circuits

More on BoundedDepth Circuits

Monotone Circuits

Formulae

Exercises

The Probabilistic Lens: Maximal Antichains

Discrepancy.

Basics

Six Standard Deviations Suffice

Linear and Hereditary Discrepancy

Lower Bounds

The BeckFiala Theorem

Exercises

The Probabilistic Lens: Unbalancing Lights

Geometry.

The Greatest Angle among Points in Euclidean Spaces

Empty Triangles Determined by Points in the Plane

Geometrical Realizations of Sign Matrices

QNets and VCDimensions of Range Spaces

Dual Shatter Functions and Discrepancy

Exercises

The Probabilistic Lens: Efficient Packing

Codes, Games and Entropy.

Codes

Liar Game

Tenure Game

Balancing Vector Game

Nonadaptive Algorithms

Half Liar Game

Entropy

Exercises

The Probabilistic Lens: An Extremal Graph

Derandomization.

The Method of Conditional Probabilities

dWise Independent Random Variables in Small Sample Spaces

Exercises

The Probabilistic Lens: Crossing Numbers, Incidences, Sums and Products

Graph Property Testing.

Property Testing

Testing colorability

Szemer æediÆs Regularity Lemma

Testing trianglefreeness

Characterizing the testable graph properties

Exercises

The Probabilistic Lens: Tur?an Numbers and Dependent Random Choice

Appendix A

Chernoff Bounds

Lower Bounds

Exercises

The Probabilistic Lens: Trianglefree Graphs Have Large Independence Numbers

Appendix B: Paul Erd" os

Papers

Conjectures

On Erd" os

Uncle Paul

References

Subject Index

Author Index

Table of Contents provided by Publisher. All Rights Reserved.