Notation ..................................................... xiii
1 Counting ..................................................... 3
1.1 The binomial theorem .................................... 3
1.2 Selection with repetitions .............................. 6
1.3 Partitions .............................................. 7
1.4 Double counting ......................................... 8
1.5 The averaging principle ................................ 11
1.6 The inclusion-exclusion principle ...................... 13
Exercises ................................................... 16
2 Advanced Counting ........................................... 23
2.1 Bounds on intersection size ............................ 23
2.2 Graphs with no 4-cycles ................................ 24
2.3 Graphs with no induced 4-cycles ........................ 26
2.4 Zarankiewicz's problem ................................. 29
2.5 Density of 0-1 matrices ................................ 33
2.6 The Lovász-Stein theorem ............................... 34
2.6.1 Covering designs .................................... 36
Exercises ................................................... 37
3 Probabilistic Counting ...................................... 41
3.1 Probabilistic preliminaries ............................ 41
3.2 Tournaments ............................................ 44
3.3 Universal sets ......................................... 45
3.4 Covering by bipartite cliques .......................... 46
3.5 2-colorable families ................................... 47
3.6 The choice number of graphs ............................ 49
Exercises ................................................... 50
Part I The Classics
4 The Pigeonhole Principle .................................... 53
4.1 Some quickies .......................................... 53
4.2 The Erdős-Szekeres theorem ............................. 55
4.3 Mantel's theorem ....................................... 56
4.4 Turan's theorem ........................................ 58
4.5 Dirichlet's theorem .................................... 59
4.6 Swell-colored graphs ................................... 60
4.7 The weight shifting argument ........................... 61
4.8 Schur's theorem ........................................ 63
4.9 Ramseyan theorems for graphs ........................... 65
4.10 Ramsey's theorem for sets ............................. 68
Exercises ................................................... 70
5 Systems of Distinct Representatives ......................... 77
5.1 The marriage theorem ................................... 77
5.2 Two applications ....................................... 79
5.2.1 Latin rectangles ................................ 79
5.2.2 Decomposition of doubly stochastic matrices ..... 80
5.3 Min-max theorems ....................................... 81
5.4 Matchings in bipartite graphs .......................... 82
Exercises ................................................... 85
6 Sunflowers .................................................. 89
6.1 The sunflower lemma .................................... 89
6.2 Modifications .......................................... 91
6.2.1 Relaxed core .................................... 91
6.2.2 Relaxed disjointness ............................ 92
6.3 Applications ........................................... 9З
6.3.1 The number of minterms .......................... 93
6.3.2 Small depth formulas ............................ 94
Exercises ................................................... 96
7 Intersecting Families ....................................... 99
7.1 Ultrafilters and Helly property ........................ 99
7.2 The Erdős-Ko-Rado theorem ............................. 100
7.3 Fisher's inequality ................................... 101
7.4 Maximal intersecting families ......................... 102
7.5 Cross-intersecting families ........................... 104
Exercises .................................................. 105
Part II Extremal Set Theory
8 Chains and Antichains ...................................... 107
8.1 Decomposition in chains and antichains ................ 108
8.2 Application: the memory allocation problem ............ 110
8.3 Spener's theorem ...................................... 111
8.4 The Bollobás theorem .................................. 112
8.5 Strong systems of distinct representatives ............ 115
8.6 Union-free families ................................... 116
Exercises .................................................. 117
9 Blocking Sets and the Duality .............................. 119
9.1 Duality ............................................... 119
9.2 The blocking number ................................... 121
9.3 Helly-type theorems ................................... 122
9.4 Blocking sets and decision trees ...................... 123
9.5 Blocking sets and monotone circuits ................... 126
Exercises .................................................. 132
10 Density and Universality ................................... 135
10.1 Dense sets ............................................ 135
10.2 Hereditary sets ....................................... 136
10.3 Matroids and approximation ............................ 139
10.4 The Kruskal-Katona theorem ............................ 143
10.5 Universal sets ........................................ 148
10.6 Paley graphs .......................................... 149
10.7 Full graphs ........................................... 151
Exercises .................................................. 153
11 Witness Sets and Isolation ................................. 155
11.1 Bondy's theorem ....................................... 155
11.2 Average witnesses ..................................... 156
11.3 The isolation lemma ................................... 159
11.4 Isolation in politics: the dictator paradox ........... 160
Exercises .................................................. 162
12 Designs .................................................... 165
12.1 Regularity ............................................ 166
12.2 Finite linear spaces .................................. 167
12.3 Difference sets ....................................... 168
12.4 Projective planes ..................................... 169
12.4.1 The construction ............................... 171
12.4.2 Bruen's theorem ................................ 172
12.5 Resolvable designs .................................... 173
12.5.1 Affine planes .................................. 174
Exercises .................................................. 175
Part III The Linear Algebra Method
13 The Basic Method ........................................... 179
13.1 The linear algebra background ......................... 179
13.2 Graph decompositions .................................. 185
13.3 Inclusion matrices .................................... 186
13.4 Disjointness matrices ................................. 187
13.5 Two-distance sets ..................................... 189
13.6 Sets with few intersection sizes ...................... 190
13.7 Constructive Ramsey graphs ............................ 191
13.8 Zero-patterns of polynomials .......................... 192
Exercises .................................................. 193
14 Orthogonality and Rank Arguments ........................... 197
14.1 Orthogonal coding ..................................... 197
14.2 Balanced pairs ........................................ 198
14.3 Hadamard matrices ..................................... 200
14.4 Matrix rank and Ramsey graphs ......................... 203
14.5 Lower bounds for boolean formulas ..................... 205
14.5.1 Reduction to set-covering ...................... 205
14.5.2 The rank lower bound ........................... 207
Exercises .................................................. 210
15 Eigenvalues and Graph Expansion ............................ 213
15.1 Expander graphs ....................................... 213
15.2 Spectral gap and the expansion ........................ 214
15.2.1 Ramanujan graphs ............................... 218
15.3 Expanders and derandomization ......................... 220
Exercises .................................................. 221
16 The Polynomial Method ...................................... 223
16.1 DeMillo-Lipton-Schwartz-Zippel lemma .................. 223
16.2 Solution of Kakeya's problem in finite fields ......... 226
16.3 Combinatorial Nullstellensatz ......................... 228
16.3.1 The permanent lemma ............................ 230
16.3.2 Covering cube by affine hyperplanes ............ 231
16.3.3 Regular subgraphs .............................. 231
16.3.4 Sum-sets ....................................... 232
16.3.5 Zero-sum sets .................................. 233
Exercises .................................................. 235
17 Combinatorics of Codes ..................................... 237
17.1 Error-correcting codes ................................ 237
17.2 Bounds on code size ................................... 239
17.3 Linear codes .......................................... 243
17.4 Universal sets from linear codes ...................... 245
17.5 Spanning diameter ..................................... 245
17.6 Expander codes ........................................ 247
17.7 Expansion of random graphs ............................ 250
Exercises .................................................. 251
Part IV The Probabilistic Method
18 Linearity of Expectation ................................... 255
18.1 Hamilton paths in tournaments ......................... 255
18.2 Sum-free sets ......................................... 256
18.3 Dominating sets ....................................... 257
18.4 The independence number ............................... 258
18.5 Crossings and incidences .............................. 259
18.5.1 Crossing number ................................ 259
18.5.2 The Szemerédi-Trotter theorem .................. 261
18.6 Far away strings ...................................... 262
18.7 Low degree polynomials ................................ 264
18.8 Maximum satisfiability ................................ 265
18.9 Hash functions ........................................ 267
18.10 Discrepancy .......................................... 268
18.11 Large deviation inequalities ......................... 273
Exercises .................................................. 276
19 The Lovász Sieve ........................................... 279
19.1 The Lovász Local Lemma ................................ 279
19.2 Disjoint cycles ....................................... 283
19.3 Colorings ............................................. 284
19.4 The k-SAT problem ..................................... 287
Exercises .................................................. 290
20 The Deletion Method ........................................ 293
20.1 Edge clique covering .................................. 293
20.2 Independent sets ...................................... 294
20.3 Coloring large-girth graphs ........................... 295
20.4 Point sets without obtuse triangles ................... 296
20.5 Affine cubes of integers .............................. 298
Exercises .................................................. 301
21 The Second Moment Method ................................... 303
21.1 The method ............................................ 303
21.2 Distinct sums ......................................... 304
21.3 Prime factors ......................................... 305
21.4 Separators ............................................ 307
21.5 Threshold for cliques ................................. 309
Exercises .................................................. 311
22 The Entropy Function ....................................... 313
22.1 Quantifying information ............................... 313
22.2 Limits to data compression ............................ 314
22.3 Shannon entropy ....................................... 318
22.4 Subadditivity ......................................... 320
22.5 Combinatorial applications ............................ 322
Exercises .................................................. 325
23 Random Walks ............................................... 327
23.1 The satisfiability problem ............................ 327
23.1.1 Papadimitriou's algorithm for 2-SAT ............ 328
23.1.2 Schöning's algorithm for 3-SAT ................. 329
23.2 Random walks in linear spaces ......................... 331
23.2.1 Small formulas for complicated functions ....... 333
23.3 Random walks and derandomization ...................... 336
Exercises .................................................. 339
24 Derandomization ............................................ 341
24.1 The method of conditional probabilities ............... 341
24.1.1 A general frame ................................ 342
24.1.2 Splitting graphs ............................... 343
24.1.3 Maximum satisfiability: the algorithmic
aspect ......................................... 344
24.2 The method of small sample spaces ..................... 345
24.2.1 Reducing the number of random bits ............. 346
24.2.2 k-wise independence ............................ 347
24.3 Sum-free sets: the algorithmic aspect ................. 350
Exercises .................................................. 352
Part V Fragments of Ramsey Theory
25 Ramseyan Theorems for Numbers .............................. 357
25.1 Arithmetic progressions ............................... 357
25.2 Szemerédi's cube lemma ................................ 360
25.3 Sum-free sets ......................................... 362
25.3.1 Kneser's theorem ............................... 363
25.4 Sum-product sets ...................................... 365
Exercises .................................................. 368
26 The Hales-Jewett Theorem ................................... 371
26.1 The theorem and its consequences ...................... 371
26.1.1 Van der Waerden's theorem ...................... 373
26.1.2 Gallai-Witt's Theorem .......................... 373
26.2 Shelah's proof of HJT ................................. 374
Exercises .................................................. 377
27 Applications in Communication Complexity ................... 379
27.1 Multi-party communication ............................. 379
27.2 The hyperplane problem ................................ 381
27.3 The partition problem ................................. 383
27.4 Lower bounds via discrepancy .......................... 385
27.5 Making non-disjoint coverings disjoint ................ 388
Exercises .................................................. 389
References .................................................... 393
Index ......................................................... 407
| 
