# Extremal Combinatorics: With Applications in Computer Science

Springer Science & Business Media, Jun 12, 2001 - Computers - 378 pages
3 Reviews
Reviews aren't verified, but Google checks for and removes fake content when it's identified
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

### References to this book

 Einführung in die KombinatorikLimited preview - 2004
 Coding, Cryptography and CombinatoricsLimited preview - 2004
All Book Search results &raquo;