Навигация
Архив выставки новых поступлений | Отечественные поступления | Иностранные поступления | Сиглы
ОбложкаJukna S. Extremal combinatorics: with applications in computer science. - Berlin; Heidelberg: Springer, 2011. - xxiii, 411 p. - Ref.: p.393-405. - Ind.: p.407-411. - ISBN 978-3-642-17363-9
 

Оглавление / Contents
 
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

Архив выставки новых поступлений | Отечественные поступления | Иностранные поступления | Сиглы
 

[О библиотеке | Академгородок | Новости | Выставки | Ресурсы | Библиография | Партнеры | ИнфоЛоция | Поиск | English]
  Пожелания и письма: www@prometeus.nsc.ru
© 1997-2014 Отделение ГПНТБ СО РАН (Новосибирск)
Статистика доступов: архив | текущая статистика
 

Документ изменен: Fri Oct 19 13:24:06 2012. Размер: 18,321 bytes.
Посещение N 259 c 23.10.2012