105,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Serie: Wiley-Interscience Series in Discrete Mathematics and Optimization
- Sprache: Englisch
Praise for the Third Edition
“Researchers of any kind of extremal combinatorics or theoretical computer science will welcome the new edition of this book.” - MAA Reviews
Maintaining a standard of excellence that establishes The Probabilistic Method as the leading reference on probabilistic methods in combinatorics, the Fourth Edition continues to feature a clear writing style, illustrative examples, and illuminating exercises. The new edition includes numerous updates to reflect the most recent developments and advances in discrete mathematics and the connections to other areas in mathematics, theoretical computer science, and statistical physics.
Emphasizing the methodology and techniques that enable problem-solving, The Probabilistic Method, Fourth Edition begins with a description of tools applied to probabilistic arguments, including basic techniques that use expectation and variance as well as the more advanced applications of martingales and correlation inequalities. The authors explore where probabilistic techniques have been applied successfully and also examine topical coverage such as discrepancy and random graphs, circuit complexity, computational geometry, and derandomization of randomized algorithms. Written by two well-known authorities in the field, the Fourth Edition features:
- Additional exercises throughout with hints and solutions to select problems in an appendix to help readers obtain a deeper understanding of the best methods and techniques
- New coverage on topics such as the Local Lemma, Six Standard Deviations result in Discrepancy Theory, Property B, and graph limits
- Updated sections to reflect major developments on the newest topics, discussions of the hypergraph container method, and many new references and improved results
The Probabilistic Method, Fourth Edition is an ideal textbook for upper-undergraduate and graduate-level students majoring in mathematics, computer science, operations research, and statistics. The Fourth Edition is also an excellent reference for researchers and combinatorists who use probabilistic methods, discrete mathematics, and number theory.
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.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 601
Veröffentlichungsjahr: 2015
Ähnliche
Table of Contents
Cover
Wiley Series in Discrete Mathematics and Optimization
Title Page
Copyright
Dedication
Preface
Acknowledgments
Part I: Methods
Chapter 1: The Basic Method
1.1 The Probabilistic Method
1.2 Graph Theory
1.3 Combinatorics
1.4 Combinatorial Number Theory
1.5 Disjoint Pairs
1.6 Independent Sets and List Coloring
1.7 Exercises
The Probabilistic Lens: The Erdős–Ko–Rado Theorem
Chapter 2: Linearity of Expectation
2.1 Basics
2.2 Splitting Graphs
2.3 Two Quickies
2.4 Balancing Vectors
2.5 Unbalancing Lights
2.6 Without Coin Flips
2.7 Exercises
The Probabilistic Lens: Brégman's Theorem
Chapter 3: Alterations
3.1 Ramsey Numbers
3.2 Independent Sets
3.3 Combinatorial Geometry
3.4 Packing
3.5 Greedy Coloring
3.6 Continuous Time
3.7 Exercises
The Probabilistic Lens: High Girth and High Chromatic Number
Chapter 4: The Second Moment
4.1 Basics
4.2 Number Theory
4.3 More Basics
4.4 Random Graphs
4.5 Clique Number
4.6 Distinct Sums
4.7 The Rödl nibble
Exercises
The Probabilistic Lens: Hamiltonian Paths
Chapter 5: The Local Lemma
5.1 The Lemma
5.2 Property
B
and Multicolored Sets of Real Numbers
5.3 Lower Bounds for Ramsey Numbers
5.4 A Geometric Result
5.5 The Linear Arboricity of Graphs
5.6 Latin Transversals
5.7 Moser's Fix-It Algorithm
5.8 Exercises
The Probabilistic Lens: Directed Cycles
Chapter 6: Correlation Inequalities
6.1 The Four Functions Theorem of Ahlswede and Daykin
6.2 The FKG Inequality
6.3 Monotone Properties
6.4 Linear Extensions of Partially Ordered Sets
6.5 Exercises
The Probabilistic Lens: Turán's Theorem
Chapter 7: Martingales and Tight Concentration
7.1 Definitions
7.2 Large Deviations
7.3 Chromatic Number
7.4 Two General Settings
7.5 Four Illustrations
7.6 Talagrand's Inequality
7.7 Applications of Talagrand's Inequality
7.8 Kim–VU Polynomial Concentration
7.9 Exercises
The Probabilistic Lens: Weierstrass Approximation Theorem
Chapter 8: The Poisson Paradigm
8.1 The Janson Inequalities
8.2 The Proofs
8.3 Brun's Sieve
8.4 Large Deviations
8.5 Counting Extensions
8.6 Counting Representations
8.7 Further Inequalities
8.8 Exercises
The Probabilistic Lens: Local Coloring
Chapter 9: Quasirandomness
9.1 The Quadratic Residue Tournaments
9.2 Eigenvalues and Expanders
9.3 Quasirandom Graphs
9.4 Szemerédi's Regularity Lemma
9.5 Graphons
9.6 Exercises
The Probabilistic Lens: Random Walks
Part II: Topics
Chapter 10: Random Graphs
10.1 Subgraphs
10.2 Clique Number
10.3 Chromatic Number
10.4 Zero–One Laws
10.5 Exercises
The Probabilistic Lens: Counting Subgraphs
Chapter 11: The Erdős–Rényi Phase Transition
11.1 An Overview
11.2 Three Processes
11.3 THE GALTON–WATSON BRANCHING PROCESS
11.4 Analysis of the Poisson Branching Process
11.5 The Graph Branching Model
11.6 The Graph and Poisson Processes Compared
11.7 The Parametrization Explained
11.8 The Subcritical Regions
11.9 The Supercritical Regimes
11.10 The Critical Window
11.11 Analogies to Classical Percolation Theory
11.12 Exercises
The Probabilistic Lens: Long paths in the supercritical regime
Chapter 12: Circuit Complexity
12.1 Preliminaries
12.2 Random Restrictions and Bounded-Depth Circuits
12.3 More on Bounded-Depth Circuits
12.4 Monotone Circuits
12.5 Formulae
12.6 Exercises
The Probabilistic Lens: Maximal Antichains
Chapter 13: Discrepancy
13.1 Basics
13.2 Six Standard Deviations Suffice
13.3 Linear and Hereditary Discrepancy
13.4 Lower Bounds
13.5 The Beck–Fiala Theorem
13.6 Exercises
The Probabilistic Lens: Unbalancing Lights
Chapter 14: Geometry
14.1 The Greatest Angle Among Points in Euclidean Spaces
14.2 Empty Triangles Determined by Points in the Plane
14.3 Geometrical Realizations of Sign Matrices
14.4 ε-Nets and Vc-Dimensions of Range Spaces
14.5 Dual Shatter Functions and Discrepancy
14.6 Exercises
The Probabilistic Lens: Efficient Packing
Chapter 15: Codes, Games, and Entropy
15.1 Codes
15.2 Liar Game
15.3 Tenure Game
15.4 Balancing vector game
15.5 Nonadaptive Algorithms
15.6 Half Liar Game
15.7 Entropy
15.8 Exercises
The Probabilistic Lens: An Extremal Graph
Chapter 16: Derandomization
16.1 The Method of Conditional Probabilities
16.2
d
-Wise Independent Random Variables in Small Sample Spaces
16.3 Exercises
The Probabilistic Lens: Crossing Numbers, Incidences, Sums and Products
Chapter 17: Graph Property Testing
17.1 Property Testing
17.2 Testing Colorability
17.3 Testing Triangle-Freeness
17.4 Characterizing the Testable Graph Properties
17.5 Exercises
The Probabilistic Lens: Turán Numbers and Dependent Random Choice
Appendix A: Bounding of Large Deviations
A.1 Chernoff Bounds
A.2 Lower Bounds
A.3 Exercises
The Probabilistic Lens: Triangle-Free Graphs Have Large Independence Numbers
Appendix B: Paul Erdős
B.1 Papers
B.2 Conjectures
B.3 On Erdős
B.4 Uncle Paul
The Probabilistic Lens: The Rich Get Richer
Appendix C: Hints to Selected Exercises
References
Author Index
Subject Index
Wiley Series in Discrete Mathematics and Optimization
End User License Agreement
Pages
xiii
xiv
xv
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
307
308
309
310
311
312
313
314
315
316
317
318
319
1
177
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
339
340
341
342
343
344
345
346
347
349
350
351
352
353
355
356
357
358
359
360
361
362
363
364
365
Guide
Cover
Table of Contents
Preface
Begin Reading
List of Illustrations
Chapter 12: Circuit Complexity
Figure 12.1 A Boolean circuit.
Wiley Series in Discrete Mathematics and Optimization
A complete list of titles in this series appears at the end of this volume.
The Probabilistic Method
Fourth edition, July 2015, Tel Aviv and New York
Noga Alon
School of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv, Israel.
Joel H. Spencer
Courant Institute of Mathematical Sciences, New York University, New York, USA
Copyright © 2016 by John Wiley & Sons, Inc. All rights reserved
Published by John Wiley & Sons, Inc., Hoboken, New Jersey
Published simultaneously in Canada
No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permission.
Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.
For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.
Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.
Library of Congress Cataloging-in-Publication Data:
Alon, Noga.
The probabilistic method / Noga Alon, Joel H. Spencer. – Fourth edition.
pages cm
Includes bibliographical references and index.
ISBN 978-1-119-06195-3 (cloth)
1. Combinatorial analysis. 2. Probabilities. I. Spencer, Joel H. II. Title.
QA164.A46 2016
511′.6–dc23
2015021599
To Nurit and Mary Ann
Preface
The probabilistic method is one of the most powerful and widely used tools applied in combinatorics. One of the major reasons for its rapid development is the important role of randomness in theoretical computer science and in statistical physics.
The interplay between discrete mathematics and computer science suggests an algorithmic point of view in the study of the probabilistic method in combinatorics, and this is the approach we tried to adopt in this book. The book thus includes a discussion of algorithmic techniques together with a study of the classical method as well as the modern tools applied in it. The first part of the book contains a description of the tools applied in probabilistic arguments, including the basic techniques that use expectation and variance, as well as the more recent applications of martingales and correlation inequalities. The second part includes a study of various topics in which probabilistic techniques have been successful. This part contains chapters on discrepancy and random graphs, as well as on several areas in theoretical computer science: Circuit Complexity, Computational Geometry, Graph Property Testing and, Derandomization of randomized algorithms. Scattered between the chapters are gems described under the heading “The Probabilistic Lens.” These are elegant proofs that are not necessarily related to the chapters after which they appear and can usually be read separately.
The basic probabilistic method can be described as follows: In order to prove the existence of a combinatorial structure with certain properties, we construct an appropriate probability space and show that a randomly chosen element in this space has the desired properties with positive probability. This method was initiated by Paul Erdős, who contributed so much to its development over a 50-year period that it seems appropriate to call it “The Erdős Method.” His contribution can be measured not only by his numerous deep results in the subject but also by the many intriguing problems and conjectures posed by him that stimulated a big portion of the research in the area.
It seems impossible to write an encyclopedic book on the probabilistic method; too many recent interesting results apply probabilistic arguments, and we do not even try to mention all of them. Our emphasis is on methodology, and we thus try to describe the ideas, and not always to give the best possible results if these are too technical to allow a clear presentation. Many of the results are asymptotic, and we use the standard asymptotic notation: for two functions f and g, we write if for all sufficiently large values of the variables of the two functions, where c is an absolute positive constant. We write if and if and . If the limit of the ratio tends to zero as the variables of the functions tend to infinity we write . Finally, denotes that ; that is, tends to when the variables tend to infinity. Each chapter ends with a list of exercises. The more difficult ones are marked by . The exercises enable readers to check their understanding of the material and also provide the possibility of using the book as a textbook.
This is the fourth edition of the book; it contains several improved results and covers various additional topics that developed extensively during the last few years. A breakthrough approach to the Local Lemma is described in Chapter 5. A new algorithmic approach to the “six standard deviations” result in discrepancy theory is presented in Chapter 12. A novel proof for the study of Property B, based on a random greedy coloring, appears in Chapter 3. In all the above cases, the algorithmic proofs provide essentially new arguments for the existence of the desired objects. A new, short section on graph limits has been added to Chapter 9. A technique for counting independent sets in graphs and its application in a graph coloring problem is described in Chapter 1. Further additions include a new Probabilistic Lens, several additional exercises, and a new appendix with hints to selected exercises.
Acknowledgments
We are very grateful to all our students and colleagues who contributed to the creation of this fourth edition through joint research, helpful discussions, and useful comments. These include Simon Blackburn, Miklós Bóna, Steve Cook, Ehud Friedgut, Oded Goldreich, Omri Ben-Eliezer, Krzysztof Choromanski, Oliver Cooley, Ohad Feldheim, Naomi Feldheim, Asaf Ferber, Laura Florescu, Lior Gishbboliner, Matan Harel, Danny Hefetz, Timo Hirscher, Rani Hod, Mihyun Kang, Joel Lewis, Nati Linial, Guy Moshkovitz, Dhruv Mubayi, Tahl Nowik, Roberto Oliveira, Ron Peled, Will Perkins, Oliver Riordan, Guy Rutenberg, Jeffrey Shallit, Asaf Shapira, Clara Shikhelman, Philipp Sprüssel, Aravind Srinivasan, John Steinberger, Elmar Teufl, Shai Vardi, Amit Weinstein, Jed Yang, Mariano Zelke and Yufei Zhao, who pointed out various inaccuracies and misprints, and suggested improvements in the presentation as well as in the results. Needless to say, the responsibility for the remaining mistakes, as well as the responsibility for the (hopefully not many) new ones, is solely ours.
Part IMethods
Chapter 1The Basic Method
What you need is that your brain is open.
–Paul Erdős
1.1 The Probabilistic Method
The probabilistic method is a powerful tool for tackling many problems in discrete mathematics. Roughly speaking, the method works as follows: trying to prove that a structure with certain desired properties exists, one defines an appropriate probability space of structures and then shows that the desired properties hold in these structures with positive probability. The method is best illustrated by examples. Here is a simple one. The Ramsey number is the smallest integer n such that in any two-coloring of the edges of a complete graph on n vertices by red and blue, either there is a red (i.e., a complete subgraph on k vertices all of whose edges are colored red) or there is a blue . Ramsey 1929 showed that is finite for any two integers k and . Let us obtain a lower bound for the diagonal Ramsey numbers .
Proposition 1.1.1
If , then . Thus for all .
Proof.
Consider a random two-coloring of the edges of obtained by coloring each edge independently either red or blue, where each color is equally likely. For any fixed set R of k vertices, let be the event that the induced subgraph of on R is monochromatic (i.e., that either all its edges are red or they are all blue). Clearly, . Since there are possible choices for R, the probability that at least one of the events occurs is at most . Thus, with positive probability, no event occurs and there is a two-coloring of without a monochromatic ; that is, . Note that if and we take , then
and hence for all .
This simple example demonstrates the essence of the probabilistic method. To prove the existence of a good coloring, we do not present one explicitly, but rather show, in a nonconstructive way, that it exists. This example appeared in a paper of P. Erdős from 1947. Although Szele had applied the probabilistic method to another combinatorial problem, mentioned in Chapter 2, already in 1943, Erdős was certainly the first to understand the full power of this method and apply it successfully over the years to numerous problems. One can, of course, claim that the probability is not essential in the proof given above. An equally simple proof can be described by counting; we just check that the total number of two-colorings of is larger than the number of those containing a monochromatic .
Moreover, since the vast majority of the probability spaces considered in the study of combinatorial problems are finite, this claim applies to most of the applications of the probabilistic method in discrete mathematics. Theoretically, this is indeed the case. However, in practice the probability is essential. It would be hopeless to replace the applications of many of the tools appearing in this book, including, for example, the second moment method, the Lovász Local Lemma and the concentration via martingales by counting arguments, even when these are applied to finite probability spaces.
The probabilistic method has an interesting algorithmic aspect. Consider, for example, the proof of Proposition 1.1.1, which shows that there is an edge two-coloring of without a monochromatic . Can we actually find such a coloring? This question, as asked, may sound ridiculous; the total number of possible colorings is finite, so we can try them all until we find the desired one. However, such a procedure may require steps; an amount of time that is exponential in the size
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
Lesen Sie weiter in der vollständigen Ausgabe!
