The Probabilistic Method, 2nd Edition

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

• ISBN13: 9780471370468
• ISBN10: 0471370460
• Edition: 2nd
• Format: Hardcover
• Copyright: 2000-08-01
• Publisher: Wiley-Interscience

Summary

The leading reference on probabilistic methods in combinatorics-now expanded and updated When it was first published in 1991, The Probabilistic Method became instantly the standard reference on one of the most powerful and widely used tools in combinatorics. Still without competition nearly a decade later, this new edition brings you up to speed on recent developments, while adding useful exercises and over 30ew material. It continues to emphasize the basic elements of the methodology, discussing in a remarkably clear and informal style both algorithmic and classical methods as well as modern applications. The Probabilistic Method, Second 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. New and revised coverage includes: * Several improved as well as new results * A continuous approach to discrete probabilistic problems * Talagrand's Inequality and other novel concentration results * A discussion of the connection between discrepancy and VC-dimension * Several combinatorial applications of the entropy function and its properties * A new section on the life and work of Paul Erdös-the developer of the probabilistic method

Author Biography

NOGA ALON, PhD, is a Baumritter Professor of Mathematics and Computer Science at Tel Aviv University. He is a member of the Israel National Academy of Sciences and received the Erd÷s Prize in 1989, the Feher Prize in 1991, and the Polya Prize in 2000. <p> . SPENCER, PhD, is Professor of Mathematics and Computer Science at the Courant Institute of New York University. He is the cofounder and coeditor of the journal Random Structures and Algorithms and is also a Sloane Foundation Fellow.

Table of Contents

Dedication	v
Preface	vii
Acknowledgments	ix
Part 1 METHODS
The Basic Method	1	(12)
The Probabilistic Method	1	(2)
Graph Theory	3	(3)
Combinatorics	6	(2)
Combinatorial Number Theory	8	(1)
Disjoint Pairs	9	(1)
Exercises	10	(3)
The Probabilistic Lens: The Erdos-Ko-Rado Theorem	12	(1)
Linearity of Expectation	13	(12)
Basics	13	(1)
Splitting Graphs	14	(2)
Two Quickies	16	(1)
Balancing Vectors	17	(1)
Unbalancing Lights	18	(2)
Without Coin Flips	20	(1)
Exercises	20	(5)
The Probabilistic Lens: Bregman's Theorem	22	(3)
Alterations	25	(16)
Ramsey Numbers	25	(2)
Independent Sets	27	(1)
Combinatorial Geometry	28	(1)
Packing	29	(1)
Recoloring	30	(3)
Continuous Time	33	(4)
Exercises	37	(4)
The Probabilistic Lens: High Girth and High Chromatic Number	38	(3)
The Second Moment	41	(22)
Basics	41	(1)
Number Theory	42	(3)
More Basics	45	(2)
Random Graphs	47	(3)
Clique Number	50	(2)
Distinct Sums	52	(1)
The Rodl Nibble	53	(5)
Exercises	58	(5)
The Probabilistic Lens: Hamiltonian Paths	60	(3)
The Local Lemma	63	(70)
The Lemma	63	(2)
Property B and Multicolored Sets of Real Numbers	65	(2)
Lower Bounds for Ramsey Numbers	67	(1)
A Geometric Result	68	(1)
The Linear Arboricity of Graphs	69	(64)
The Probabilistic Lens: Local Coloring	130	(3)
Pseudorandomness	133	(22)
The Quadratic Residue Tournaments	134	(3)
Eigenvalues and Expanders	137	(5)
Quasi Random Graphs	142	(6)
Exercises	148	(7)
The Probabilistic Lens: Random Walks	150	(5)
Part II TOPICS
Random Graphs	155	(28)
Subgraphs	156	(2)
Clique Number	158	(2)
Chromatic Number	160	(1)
Branching Processes	161	(4)
The Giant Component	165	(3)
Inside the Phase Transition	168	(3)
Zero-One Laws	171	(7)
Exercises	178	(5)
The Probabilistic Lens: Counting Subgraphs	180	(3)
Circuit Complexity	183	(16)
Preliminaries	183	(2)
Random Restrictions and Bounded-Depth Circuits	185	(4)
More on Bounded-Depth Circuits	189	(2)
Monotone Circuits	191	(3)
Formulae	194	(2)
Exercises	196	(3)
The Probabilistic Lens: Maximal Antichains	197	(2)
Discrepancy	199	(16)
Basics	199	(2)
Six Standard Deviations Suffice	201	(3)
Linear and Hereditary Discrepancy	204	(3)
Lower Bounds	207	(2)
The Beck-Fiala Theorem	209	(1)
Exercises	210	(5)
The Probabilistic Lens: Unbalancing Lights	212	(3)
Geometry	215	(16)
The Greatest Angle among Points in Euclidean Spaces	216	(1)
Empty Triangles Determined by Points in the Plane	217	(1)
Geometrical Realizations of Sign Matrices	218	(2)
&epsis;-Nets and VC-Dimensions of Range Spaces	220	(5)
Dual Shatter Functions and Discrepancy	225	(3)
Exercises	228	(3)
The Probabilistic Lens: Efficient Packing	229	(2)
Codes, Games and Entropy	231	(18)
Codes	231	(2)
Liar Game	233	(3)
Tenure Game	236	(1)
Balancing Vector Game	237	(2)
Nonadaptive Algorithms	239	(1)
Entropy	240	(5)
Exercises	245	(4)
The Probabilistic Lens: An Extremal Graph	247	(2)
Derandomization	249	(14)
The Method of Conditional Probabilities	249	(4)
d-Wise Independent Random Variables in Small Sample Spaces	253	(4)
Exercises	257	(6)
The Probabilistic Lens: Crossing Numbers, Incidences, Sums and Products	259	(4)
Appendix A: Bounding of Large Deviations	263	(12)
A.1 Bounding of Large Deviations	263	(8)
A.2 Exercises	271	(4)
The Probabilistic Lens: Triangle-free Graphs Have Large Independence Numbers	272	(3)
Appendix B: Paul Erdos	275	(8)
B.1 Papers	275	(2)
B.2 Conjectures	277	(1)
B.3 On Erdos	278	(1)
B.4 Uncle Paul	279	(4)
References	283	(12)
Subject Index	295	(4)
Author Index	299