ISBN-10:
0471535885
ISBN-13:
9780471535881
Pub. Date:
02/28/1992
Publisher:
Wiley
The Probabilistic Method / Edition 1

The Probabilistic Method / Edition 1

Hardcover

Current price is , Original price is $105.0. You

Temporarily Out of Stock Online

Please check back later for updated availability.

This item is available online through Marketplace sellers.

Overview

One of the most powerful and popular tools used in combinatorics is the probabilistic method. Describes current algorithmic techniques, applying both the classical method and the modern tools it uses. Along with a detailed description of the techniques used in probabilistic arguments, it includes basic methods which utilize expectation and variance plus recent applications of martingales and correlation inequalities. Examines discrepancy and random graphs and covers such topics as theoretical computer science, computational geometry, derandomization of randomized algorithms and more. A study of various topics using successful probabilistic techniques is included along with an Open Problems Appendix by Paul Erdos, the founder of the probabilistic method.

Product Details

ISBN-13: 9780471535881
Publisher: Wiley
Publication date: 02/28/1992
Series: Wiley Series in Discrete Mathematics and Optimization Series , #29
Edition description: Older Edition
Pages: 272
Product dimensions: 6.47(w) x 9.58(h) x 0.84(d)

About the Author

Noga Alon, PhD, is Baumritter Professor of Mathematics and Computer Science at Tel Aviv University. He is a member of the Israel National Academy of Sciences and Academia Europaea. A coeditor of the journal Random Structures and Algorithms, Dr. Alon is the recipient of the Polya Prize, The Gödel Prize, The Israel Prize, and the EMET Prize.

Joel H. 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 a Sloane Foundation Fellow. Dr. Spencer has written more than 200 published articles and is the coauthor of Ramsey Theory, Second Edition, also published by Wiley.

Read an Excerpt

Click to read or download

Table of Contents

Dedicationv
Prefacevii
Acknowledgmentsix
Part IMethods
1The Basic Method1
1.1The Probabilistic Method1
1.2Graph Theory3
1.3Combinatorics6
1.4Combinatorial Number Theory8
1.5Disjoint Pairs9
1.6Exercises10
The Probabilistic Lens: The Erdos-Ko-Rado Theorem12
2Linearity of Expectation13
2.1Basics13
2.2Splitting Graphs14
2.3Two Quickies16
2.4Balancing Vectors17
2.5Unbalancing Lights18
2.6Without Coin Flips20
2.7Exercises20
The Probabilistic Lens: Bregman's Theorem22
3Alterations25
3.1Ramsey Numbers25
3.2Independent Sets27
3.3Combinatorial Geometry28
3.4Packing29
3.5Recoloring30
3.6Continuous Time33
3.7Exercises37
The Probabilistic Lens: High Girth and High Chromatic Number38
4The Second Moment41
4.1Basics41
4.2Number Theory42
4.3More Basics45
4.4Random Graphs47
4.5Clique Number50
4.6Distinct Sums52
4.7The Rodl Nibble53
4.8Exercises58
The Probabilistic Lens: Hamiltonian Paths60
5The Local Lemma63
5.1The Lemma63
5.2Property B and Multicolored Sets of Real Numbers65
5.3Lower Bounds for Ramsey Numbers67
5.4A Geometric Results68
5.5The Linear Arboricity of Graphs69
5.6Latin Transversals73
5.7The Algorithmic Aspect74
5.8Exercises77
The Probabilistic Lens: Directed Cycles78
6Correlation Inequalities81
6.1The Four Functions Theorem of Ahlswede and Daykin82
6.2The FKG Inequality84
6.3Monotone Properties86
6.4Linear Extensions of Partially Ordered Sets88
6.5Exercises90
The Probabilistic Lens: Turan's Theorem91
7Martingales and Tight Concentration93
7.1Definitions93
7.2Large Deviations95
7.3Chromatic Number96
7.4Two General Settings99
7.5Four Illustrations103
7.6Talagrand's Inequality105
7.7Applications of Talagrand's Inequality108
7.8Kim-Vu Polynomial Concentration110
7.9Exercises112
The Probabilistic Lens: Weierstrass Approximation Theorem113
8The Poisson Paradigm115
8.1The Janson Inequalities115
8.2The Proofs117
8.3Brun's Sieve119
8.4Large Deviations122
8.5Counting Extensions123
8.6Counting Representations125
8.7Further Inequalities128
8.8Exercises129
The Probabilistic Lens: Local Coloring130
9Pseudorandomness133
9.1The Quadratic Residue Tournaments134
9.2Eigenvalues and Expanders137
9.3Quasi Random Graphs142
9.4Exercises148
The Probabilistic Lens: Random Walks150
Part IITopics
10Random Graphs155
10.1Subgraphs156
10.2Clique Number158
10.3Chromatic Number160
10.4Branching Processes161
10.5The Giant Component165
10.6Inside the Phase Transition168
10.7Zero-One Laws171
10.8Exercises178
The Probabilistic Lens: Counting Subgraphs180
11Circuit Complexity183
11.1Preliminaries183
11.2Random Restrictions and Bounded-Depth Circuits185
11.3More on Bounded-Depth Circuits189
11.4Monotone Circuits191
11.5Formulae194
11.6Exercises196
The Probabilistic Lens: Maximal Antichains197
12Discrepancy199
12.1Basics199
12.2Six Standard Deviations Suffice201
12.3Linear and Hereditary Discrepancy204
12.4Lower Bounds207
12.5The Beck-Fiala Theorem209
12.6Exercises210
The Probabilistic Lens: Unbalancing Lights212
13Geometry215
13.1The Greatest Angle among Points in Euclidean Spaces216
13.2Empty Triangles Determined by Points in the Plane217
13.3Geometrical Realizations of Sign Matrices218
13.4[epsilon]-Nets and VC-Dimensions of Range Spaces220
13.5Dual Shatter Functions and Discrepancy225
13.6Exercises228
The Probabilistic Lens: Efficient Packing229
14Codes, Games and Entropy231
14.1Codes231
14.2Liar Game233
14.3Tenure Game236
14.4Balancing Vector Game237
14.5Nonadaptive Algorithms239
14.6Entropy240
14.7Exercises245
The Probabilistic Lens: An Extremal Graph247
15Derandomization249
15.1The Method of Conditional Probabilities249
15.2d-Wise Independent Random Variables in Small Sample Spaces253
15.3Exercises257
The Probabilistic Lens: Crossing Numbers, Incidences, Sums and Products259
Appendix ABounding of Large Deviations263
A.1Bounding of Large Deviations263
A.2Exercises271
The Probabilistic Lens: Triangle-free Graphs Have Large Independence Numbers272
Appendix BPaul Erdos275
B.1Papers275
B.2Conjectures277
B.3On Erdos278
B.4Uncle Paul279
References283
Subject Index295
Author Index299

Customer Reviews

Most Helpful Customer Reviews

See All Customer Reviews