Extremal Combinatorics: With Applications in Computer Science

Front Cover
Springer Science & Business Media, Jun 12, 2001 - Computers - 378 pages
3 Reviews
Combinatorial mathematics has been pursued since time immemorial, and at a reasonable scientific level at least since Leonhard Euler (1707-1783). It ren dered many services to both pure and applied mathematics. Then along came the prince of computer science with its many mathematical problems and needs - and it was combinatorics that best fitted the glass slipper held out. Moreover, it has been gradually more and more realized that combinatorics has all sorts of deep connections with "mainstream areas" of mathematics, such as algebra, geometry and probability. This is why combinatorics is now apart of the standard mathematics and computer science curriculum. This book is as an introduction to extremal combinatorics - a field of com binatorial mathematics which has undergone aperiod of spectacular growth in recent decades. The word "extremal" comes from the nature of problems this field deals with: if a collection of finite objects (numbers, graphs, vectors, sets, etc. ) satisfies certain restrictions, how large or how small can it be? For example, how many people can we invite to a party where among each three people there are two who know each other and two who don't know each other? An easy Ramsey-type argument shows that at most five persons can attend such a party. Or, suppose we are given a finite set of nonzero integers, and are asked to mark an as large as possible subset of them under the restriction that the sum of any two marked integers cannot be marked.
 

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

Other editions - View all

Common terms and phrases

References to this book

All Book Search results »