Extremal Combinatorics: With Applications in Computer Science

Front Cover
Springer Science & Business Media, 2001 - Computers - 375 pages
3 Reviews
The book is a concise, self-contained and up-to-date introduction to extremal combinatorics for non-specialists. Strong emphasis is made on theorems with particularly elegant and informative proofs which may be called gems of the theory. A wide spectrum of most powerful combinatorial tools is presented: methods of extremal set theory, the linear algebra method, the probabilistic method and fragments of Ramsey theory. A throughout discussion of some recent applications to computer science motivates the liveliness and inherent usefulness of these methods to approach problems outside combinatorics. No special combinatorial or algebraic background is assumed. All necessary elements of linear algebra and discrete probability are introduced before their combinatorial applications. Aimed primarily as an introductory text for graduates, it provides also a compact source of modern extremal combinatorics for researchers in computer science and other fields of discrete mathematics.
  

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

What This Book Is About
1
Notation
5
1 Counting
11
12 Selection with repetitions
13
13 Partitions
14
15 The averaging principle
16
Exercises
19
2 Advanced Counting
23
1441 Universal sets from linear codes
182
145 The flipping cards game
184
Exercises
186
15 Orthogonality and Rank Arguments
191
1512 A bribery party
192
1513 Hadamard matrices
194
152 Rank arguments
196
1522 Lower bounds for boolean formulas
197

22 Zarankiewiczs problem
25
23 Density of 01 matrices
27
Exercises
29
3 The Principle of Inclusion and Exclusion
32
32 The number of derangements
34
Exercises
35
4 The Pigeonhole Principle
37
42 The ErdosSzekeres theorem
38
43 Mantels theorem
40
44 Turans theorem
41
45 Dirichlets theorem
42
46 Swellcolored graphs
43
47 The weight shifting argument
45
48 Pigeonhole and resolution
47
482 Hakens lower bound
48
Exercises
51
5 Systems of Distinct Representatives
55
52 Two applications
57
522 Decomposition of doubly stochastic matrices
58
53 Minmax theorems
59
54 Matchings in bipartite graphs
60
Exercises
63
6 Colorings
65
62 The averaging argument
67
622 The number of mixed triangles
68
the algorithmic aspect
71
Exercises
73
7 Sunflowers
79
72 Modifications
81
722 Relaxed disjointness
82
73 Applications
83
732 Small depth formulas
84
Exercises
86
8 Intersecting Families
89
82 Finite ultrafilters
90
83 Maximal intersecting families
91
84 A Hellytype result
93
Exercises
95
9 Chains and Antichains
97
911 Symmetric chains
99
the memory allocation problem
100
92 Antichains
101
922 Bollobass theorem
102
923 Strong systems of distinct representatives
105
924 Unionfree families
106
Exercises
107
10 Blocking Sets and the Duality
109
102 The blocking number
111
103 Generalized Helly theorems
112
104 Decision trees
114
1041 Depth versus certificate complexity
115
1042 Block sensitivity
116
105 The switching lemma
117
106 Monotone circuits
121
1061 The lower bounds criterion
122
1062 Explicit lower bounds
125
Exercises
130
11 Density and Universality
133
112 Hereditary sets
134
113 Universal sets
136
1131 Isolated neighbor condition
137
1132 Paley graphs
138
114 Full graphs
140
Exercises
141
12 Witness Sets and Isolation
143
122 Average witnesses
144
123 The isolation lemma
147
the dictator paradox
150
Exercises
152
13 Designs
153
132 Finite linear spaces
155
133 Difference sets
156
134 Projective planes
157
1341 The construction
158
1342 Bruens theorem
159
135 Resolvable designs
161
1351 Affine planes
162
1352 Blocking sets in affine planes
163
Exercises
165
14 The Basic Method
169
142 Spaces of incidence vectors
172
1422 Inclusion matrices
173
1423 Disjointness matrices
175
143 Spaces of polynomials
176
1431 Twodistance sets
177
1432 Sets with few intersection sizes
178
1433 Constructive Ramsey graphs
179
1434 Bollobas theorem another proof
180
144 Combinatorics of linear spaces
181
Exercises
203
16 Span Programs
205
162 Span programs and switching networks
206
1631 Threshold functions
207
1632 Nonbipartite graphs
208
1634 A lower bound for threshold functions
211
164 A general lower bound
212
165 Explicit selfavoiding families
214
Exercises
216
17 Basic Tools
221
172 Elementary tools
224
173 Advanced tools
225
Exercises
227
18 Counting Sieve
229
182 Van der Waerdens theorem
230
183 Tournaments
231
185 The existence of small universal sets
232
186 Crossintersecting families
233
Exercises
236
19 The Lovasz Sieve
237
192 Counting sieve for almost independence
239
193 Applications
240
1932 Hashing functions
243
Exercises
244
20 Linearity of Expectation
245
202 Sumfree sets
246
203 Dominating sets
247
205 Low degree polynomials
248
206 Maximum satisfiability
250
207 Hashing functions
251
208 Submodular complexity measures
253
209 Discrepancy
256
matrix multiplication
259
Exercises
260
21 The Deletion Method
263
212 Independent sets
264
213 Coloring largegirth graphs
265
214 Point sets without obtuse triangles
266
215 Covering designs
268
216 Affine cubes of integers
269
Exercises
272
22 The Second Moment Method
273
222 Separators
274
223 Threshold for cliques
276
Exercises
278
23 The Entropy Function
279
232 Subadditivity
280
233 Combinatorial applications
282
Exercises
285
24 Random Walks
286
242 The best bet for simpletons
288
243 Small formulas for complicated functions
290
244 Random walks and search problems
294
2441 Long words over a small alphabet
295
2442 Short words over a large alphabet
296
Exercises
298
25 Randomized Algorithms
299
252 Verifying the equality of long strings
302
254 A mincut algorithm
304
Exercises
306
26 Derandomization
307
2611 A general frame
308
2612 Splitting graphs
309
the algorithmic aspect
310
262 The method of small sample spaces
312
the algorithmic aspect
316
Exercises
317
27 Ramseys Theorem
321
272 Ramseys theorem for graphs
322
273 Ramseys theorem for sets
324
274 Schurs theorem
326
convex polygons
327
28 Ramseyan Theorems for Numbers
329
282 Zerosum sets
332
283 Szemeredis cube lemma
334
Exercises
336
29 The HalesJewett Theorem
337
2911 Van der Waerdens theorem
338
2912 Gallai Witts Theorem
339
292 Shelahs proof of HJT
340
multiparty games
343
the hyperplane problem
344
the matrix product problem
348
Exercises
349
What Next?
351
References
353
Name Index
367
Subject Index
371
Copyright

Common terms and phrases

References to this book

All Book Search results »

Bibliographic information