Building bridges between mathematics and computer science

Title Page......Page 4
Copyright Page......Page 5
Table of Contents......Page 6
Preface......Page 8
Curriculum Vitae of László Lovász......Page 11
Books:......Page 14
Research papers:......Page 15
Expository papers:......Page 27
1. Introduction......Page 29
2. The Steinitz lemma......Page 30
3. The story of the Steinitz lemma......Page 32
4. Signed sum......Page 34
5. Signing vector sequences......Page 36
6. Partitioning a sequence......Page 39
7. A transference theorem......Page 41
References......Page 42
1. Row-Column Games.......Page 44
2. Exact results.......Page 47
3. The Core-Density and the Surplus.......Page 50
4. Remarks.......Page 53
5. Regular graphs – local randomness.......Page 55
6. Can we use the Lovász Local Lemma in games?......Page 56
7. When the Lovász Local Lemma successfully predicts the truth: examples in Tic-Tac-Toe like games.......Page 58
8. How sharp is Theorem 1?......Page 65
1.......Page 67
2.......Page 70
3. Inevitable surplus is trivial.......Page 73
4. Discrepancy and variance.......Page 76
1. What is the difficulty in general?......Page 80
2. An alternative approach.......Page 81
3. Global balancing.......Page 85
4. An average argument.......Page 89
4. Proof of Theorem 2: the Upper Bound......Page 92
References......Page 99
1. Introduction......Page 100
2. Deformable Polygon Representation......Page 103
3. Construction and its Proof......Page 107
4. Mincuts and Near-Mincuts......Page 122
5. Tree Hierarchy......Page 124
6. Size of the Family......Page 129
References......Page 131
1. Introduction......Page 133
2.1. Basic cases......Page 136
2.2. Extensions......Page 140
3.1. Simultaneous coverings......Page 147
3.2. Applications to bipartite graphs and digraphs......Page 154
3.3. Algorithmic aspects......Page 156
References......Page 158
1. Introduction......Page 161
2.1. Basics......Page 164
2.2. The braid arrangement......Page 166
2.3. Cell complexes and zonotopes......Page 168
2.4. The permutohedron and the k-equal arrangements......Page 169
3.1. Basics......Page 172
3.2. Cell complexes......Page 175
3.3. Complexified R-arrangements......Page 176
4. Random Walks......Page 178
4.1. Walks on semigroups......Page 179
4.2. Walks on R-arrangements......Page 181
4.3. Walks on C-arrangements......Page 182
4.4. Walks on libraries......Page 184
4.5. Walks on greedoids......Page 189
5. Appendix......Page 193
5.1. A generalized Zaslavsky formula......Page 194
5.2. Lattice of intervals......Page 195
5.3. Interval greedoids......Page 196
References......Page 198
1. Introduction......Page 200
2. Old and New Results in the Plane......Page 201
3. Solution of Kakeya’s Problem in the Plane......Page 204
4. Applications to Dual Blocking Sets......Page 209
5. Old and New Results in Higher Dimensions......Page 211
References......Page 213
1. Introduction......Page 214
1.1. Measure triples......Page 215
1.2. SR-systems......Page 216
1.2.1. Using SR-systems to define ε-regularity.......Page 217
2. The main result......Page 219
3.1. Equitable partitions......Page 220
3.2. Regularity lemmas for k-graphs......Page 221
3.3. Regularity lemmas for the cube [0, 1]k......Page 222
3.4. Regularity lemmas for functions and matrices......Page 223
3.4.1. A regularity lemma for matrices.......Page 224
4. Proofs......Page 225
4.1. Proof of Theorem 13......Page 226
4.2. Proof of Lemma 14......Page 231
4.3. Proof of Theorem 23......Page 232
References......Page 234
1. Introduction......Page 236
1.1. Previous work......Page 238
1.2. Results......Page 241
2. Algorithm......Page 245
2.1. Parallel pancakes......Page 246
3.1. Matrix properties......Page 247
3.2. The Fisher criterion and isotropy......Page 249
3.3.1. Single Component.......Page 252
3.3.2. Mixture moments.......Page 255
3.4. Sample convergence......Page 259
4. Finding a Vector near the Fisher Subspace......Page 262
4.1. Mean shift......Page 264
4.2. Spectral method......Page 265
5. Recursion......Page 270
References......Page 275
1. Introduction......Page 277
1.1. Motivation and related work......Page 280
2. Distinguished Cycles Shorter than log n......Page 282
3. Distinguished Cycles Longer than log n......Page 288
3.1. A digression......Page 289
3.2. Back to the main proof......Page 291
3.3. A negative example......Page 295
3.4. Extensions......Page 296
4. Nontrivial Cycles of Length O(log n)......Page 298
References......Page 301
1. Introduction......Page 302
2. The Case k = l + 1......Page 305
3. The General Case......Page 307
5. Finding a Large Subset......Page 309
6. An Application to Restricted Sums......Page 311
References......Page 313
1. Introduction......Page 314
2. Proof of the Square-form Theorem......Page 317
2.1. Decoupling......Page 319
3. Proof of Theorems 2 and 3......Page 321
References......Page 323
Introduction......Page 325
Instance......Page 328
What is Known......Page 329
Extensions......Page 330
Motivation......Page 331
What is Known......Page 332
Extensions......Page 334
Task......Page 335
Extensions......Page 336
Motivation......Page 337
Task......Page 338
Extensions......Page 339
Motivation......Page 340
Task......Page 341
Importance......Page 342
Instance......Page 343
Extensions......Page 345
Motivation......Page 346
What is Known......Page 348
Importance......Page 349
What is Known......Page 350
Motivation......Page 351
Challenge......Page 352
Extensions......Page 353
Instance......Page 354
Extensions......Page 355
References......Page 356
4. Regular Partitions of Sparse Graphs......Page 361
1.1. Dense graphs......Page 362
1.2. Sparse graphs......Page 363
2. Measuring Sparsity......Page 365
2.1. Shallow minors and grads......Page 366
2.2. Shallow topological minors and top-grads......Page 368
2.3. Hajós or Hadwiger?......Page 369
2.4. Stability with respect to lexicographic product......Page 371
3.1.1. Limits.......Page 372
3.2. When is a class sparse or dense?......Page 373
3.3. Within the nowhere dense world......Page 375
3.4. Classes with bounded expansion......Page 377
3.5. Proper minor closed classes......Page 379
3.6. The full picture......Page 380
4.2. Tree-depth......Page 382
4.3. Generalized coloring numbers......Page 385
4.4. Low tree-width coloring......Page 387
4.5. Low tree-depth coloring and p-centered colorings......Page 388
4.6. Algorithmic considerations......Page 390
4.6.1. Computing a Transitive Fraternal Augmentation.......Page 391
5. Algorithmic Applications......Page 392
5.1. Subgraph isomorphism problem......Page 393
5.3. Existential first-order properties......Page 394
5.4. Dominating sets......Page 395
5.5. Induced matchings......Page 397
5.6. Vertex separators......Page 398
6.1. Restricted dualities......Page 399
6.2. Homomorphism preservation......Page 402
6.3. Richness of first order......Page 406
7.1. Polynomial dependence......Page 408
7.2.1. Classes of nowhere dense graphs.......Page 409
7.2.2. Bounded expansion classes.......Page 410
References......Page 411
1. Introduction and a Brief History......Page 419
2. n-extendability in General......Page 421
3. Matching Extension in Embedded Graphs......Page 425
4. Restricted Matching Extension: the E(m, n) Properties......Page 428
5. Variations on a Theme......Page 433
6. Bricks and Braces: a Brief Outline......Page 434
7. Pfaffian Graphs......Page 437
References......Page 440
1. Introduction......Page 447
2. Top......Page 453
2.1. The Structure of Top. An Informal Presentation......Page 457
3. Adjacent n Simplicies......Page 461
4. Which k 1 Faces are Interior to Top?......Page 462
5. Lattice Translates of Interior Simplicies......Page 464
6. Intervals in Top [g]......Page 465
7.1. Boundary Intervals in Top [g]......Page 470
8. The Behavior of Top under Continuous Changes in a0......Page 471
9. What is Next?......Page 475
References......Page 477
1. Introduction......Page 479
2. The Characterization......Page 480
3. Some Framework......Page 481
4. Derivatives......Page 483
5. Proof of Theorem 1......Page 484
6. Derivation of Szegedy’s Theorem......Page 488
7. Uniqueness of b......Page 489
References......Page 490
1. Introduction......Page 491
2. The Sum-Product Problem......Page 492
2.1. The Sum-Product graph......Page 493
2.2. The spectral bound......Page 494
3. 3-term Arithmetic Progressions......Page 495
4. Sidon functions......Page 497
5. Incidence Bounds on Pseudolines......Page 501
References......Page 504
2. Common Elements......Page 506
3. Lovász......Page 508
4. Janson......Page 511
References......Page 514
1. Introduction......Page 516
2. Freiman’s Structural Theorem......Page 520
3. Structure of Zero-Sum-Free Sets......Page 521
3.2. The structure of relatively large zero-sum-free sets......Page 522
4. Incomplete Sets......Page 523
4.1. The structure of relatively large incomplete sets......Page 524
4.2. The structure of incomplete sequences......Page 525
5. Incomplete Sets in a General Abelian Group......Page 526
6. Structures in SA......Page 528
6.1. Folkman conjectures on infinite arithmetic progressions......Page 529
6.2. Erdős conjecture on square-sum-free sets......Page 530
7. Inverse Littlewood–Offord Theorems and Random Matrices......Page 531
References......Page 533