Extremal Combinatorics: With Applications in Computer Science

Stasys Jukna

Springer Science & Business Media, Jun 12, 2001 - Computers - 378 pages

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.

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
• 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
• 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
• 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

Bibliographic information

• Title: Extremal Combinatorics: With Applications in Computer Science; Texts in Theoretical Computer Science. An EATCS Series
• Author: Stasys Jukna
• Edition: illustrated
• Publisher: Springer Science & Business Media, 2001
• ISBN: 3540663134, 9783540663133
• Length: 378 pages
• Subjects: Computers / Computer Science; Computers / Data Processing; Computers / Information Technology; Mathematics / Applied; Mathematics / Combinatorics; Mathematics / Discrete Mathematics; Mathematics / History & Philosophy; Mathematics / Logic; Mathematics / Probability & Statistics / General