## Extremal Combinatorics: With Applications in Computer ScienceThe 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 |

351 | |

353 | |

367 | |

371 | |

### Common terms and phrases

0-1 vectors 2-colorable algorithm antichain apply argument assignment bipartite graph bits blocking set boolean function claim clauses clique color column combinatorial computed consider contains at least coordinates define denote disjoint distinct representatives elements Erdos exactly Exercise exists family F family of subsets finite fixed formula function f given graph G Hadamard matrix hence Hint implies inequality input integers intersecting labeled Lemma length Let F Let G linear algebra linearly independent literals lower bound Markov's inequality matrix member of F minimal number minterms monochromatic monomials monotone circuits n-element set neighbors node nonzero obtain pair Paley graphs path permutation pigeonhole principle players points polynomial possible Prob probabilistic probability projective plane Proposition Ramsey Theory Ramsey's theorem random variable result rows satisfying Sect sequence strings subgraph sum-free Suppose switching lemma system of distinct triangle Turan's theorem upper bound vertex vertices