Building Bridges (eBook)

Gyula O.H. Katona, President of the Bolyai Society, member of the Hungarian Academy of Sciences, honorary member of the Bulgarian Academy of Sciences Martin Grötschel, Secretary of the International Mathematical Union, Vice President of Konrad-Zuse-Zentrum Berlin

Title Page 4
Copyright Page 5
Table of Contents 6
Preface 8
Curriculum Vitae of László Lovász 11
Publications of László Lovász 14
Books: 14
Research papers: 15
Expository papers: 27
On the Power of Linear Dependencies IMRE BÁRÁNY 29
1. Introduction 29
2. The Steinitz lemma 30
3. The story of the Steinitz lemma 32
4. Signed sum 34
5. Signing vector sequences 36
6. Partitioning a sequence 39
7. A transference theorem 41
References 42
Surplus of Graphs and the Lovász Local Lemma JÓZSEF BECK 44
1. What is the Surplus? 44
1. Row-Column Games. 44
2. Exact results. 47
3. The Core-Density and the Surplus. 50
4. Remarks. 53
5. Regular graphs – local randomness. 55
6. Can we use the Lovász Local Lemma in games? 56
7. When the Lovász Local Lemma successfully predicts the truth: examples in Tic-Tac-Toe like games. 58
8. How sharp is Theorem 1? 65
2. Potential Technique 67
1. 67
2. 70
3. Inevitable surplus is trivial. 73
4. Discrepancy and variance. 76
3. Proof of Theorem 1 80
1. What is the difficulty in general? 80
2. An alternative approach. 81
3. Global balancing. 85
4. An average argument. 89
4. Proof of Theorem 2: the Upper Bound 92
References 99
Deformable Polygon Representation and Near-Mincuts ANDRÁS A. BENCZÚR* and MICHEL X. GOEMANS† 100
1. Introduction 100
2. Deformable Polygon Representation 103
3. Construction and its Proof 107
4. Mincuts and Near-Mincuts 122
5. Tree Hierarchy 124
6. Size of the Family 129
7. Conclusion 131
References 131
Variations for Lovsáz’ Submodular Ideas KRISTÓF BÉRCZI and ANDRÁS FRANK* 133
1. Introduction 133
2. Packing Arborescences 136
2.1. Basic cases 136
2.2. Extensions 140
3. Covering Supermodular Bi-set Functions by Digraphs 147
3.1. Simultaneous coverings 147
3.2. Applications to bipartite graphs and digraphs 154
3.3. Algorithmic aspects 156
References 158
Random Walks, Arrangements, Cell Complexes, Greedoids, and Self-organizing Libraries ANDERS BJÖRNER 161
1. Introduction 161
2. Real Hyperplane Arrangements 164
2.1. Basics 164
2.2. The braid arrangement 166
2.3. Cell complexes and zonotopes 168
2.4. The permutohedron and the k-equal arrangements 169
3. Complex Hyperplane Arrangements 172
3.1. Basics 172
3.2. Cell complexes 175
3.3. Complexified R-arrangements 176
4. Random Walks 178
4.1. Walks on semigroups 179
4.2. Walks on R-arrangements 181
4.3. Walks on C-arrangements 182
4.4. Walks on libraries 184
4.5. Walks on greedoids 189
5. Appendix 193
5.1. A generalized Zaslavsky formula 194
5.2. Lattice of intervals 195
5.3. Interval greedoids 196
References 198
The Finite Field Kakeya Problem AART BLOKHUIS and FRANCESCO MAZZOCCA 200
1. Introduction 200
2. Old and New Results in the Plane 201
3. Solution of Kakeya’s Problem in the Plane 204
4. Applications to Dual Blocking Sets 209
5. Old and New Results in Higher Dimensions 211
References 213
An Abstract Szemerédi Regularity Lemma BÉLA BOLLOBÁS* and VLADIMIR NIKIFOROV 214
1. Introduction 214
1.1. Measure triples 215
1.2. SR-systems 216
1.2.1. Using SR-systems to define e-regularity. 217
1.3. Partitions in measure triples 219
1.3.1. Bounding families of partitions. 219
2. The main result 219
3. Applications 220
3.1. Equitable partitions 220
3.2. Regularity lemmas for k-graphs 221
3.2.1. A regularity lemma for k-partite k-graphs. 222
3.3. Regularity lemmas for the cube [0, 1]k 222
3.4. Regularity lemmas for functions and matrices 223
3.4.1. A regularity lemma for matrices. 224
4. Proofs 225
4.1. Proof of Theorem 13 226
4.2. Proof of Lemma 14 231
4.3. Proof of Theorem 23 232
References 234
Isotropic PCA and Affine-Invariant Clustering S. CHARLES BRUBAKER and SANTOSH S. VEMPALA 236
1. Introduction 236
1.1. Previous work 238
1.2. Results 241
2. Algorithm 245
2.1. Parallel pancakes 246
2.2. Overview of analysis 247
3. Preliminaries 247
3.1. Matrix properties 247
3.2. The Fisher criterion and isotropy 249
3.3. Approximation of the reweighted moments 252
3.3.1. Single Component. 252
3.3.2. Mixture moments. 255
3.4. Sample convergence 259
3.5. Perturbation lemma 262
4. Finding a Vector near the Fisher Subspace 262
4.1. Mean shift 264
4.2. Spectral method 265
5. Recursion 270
6. Conclusion 275
References 275
Small Linear Dependencies for Binary Vectors of Low Weight URIEL FEIGE 277
1. Introduction 277
1.1. Motivation and related work 280
2. Distinguished Cycles Shorter than log n 282
3. Distinguished Cycles Longer than log n 288
3.1. A digression 289
3.2. Back to the main proof 291
3.3. A negative example 295
3.4. Extensions 296
4. Nontrivial Cycles of Length O(log n) 298
References 301
Plünnecke’s Inequality for Different Summands KATALIN GYARMATI*, MÁTÉ MATOLCSI† and IMRE Z. RUZSA‡ 302
1. Introduction 302
2. The Case k = l + 1 305
3. The General Case 307
4. Removing the Constant 309
5. Finding a Large Subset 309
6. An Application to Restricted Sums 311
References 313
Decoupling and Partial Independence RAVI KANNAN 314
1. Introduction 314
2. Proof of the Square-form Theorem 317
2.1. Decoupling 319
3. Proof of Theorems 2 and 3 321
References 323
Combinatorial Problems in Chip Design BERNHARD KORTE and JENS VYGEN 325
Introduction 325
1. Floorplanning 328
Motivation 328
Instance 328
Task 329
Challenge 329
What is Known 329
Extensions 330
Importance 331
2. Lower Bounds for Placement 331
Motivation 331
Instance 332
Task 332
Challenge 332
What is Known 332
Extensions 334
Importance 335
3. Legalizing a Placement 335
Motivation 335
Instance 335
Task 335
Challenge 336
What is Known 336
Extensions 336
Importance 337
4. Steiner Trees Minimizing Elmore Delay 337
Motivation 337
Instance 338
Task 338
Challenge 339
What is Known 339
Extensions 339
Importance 340
5. Resource Sharing and Multiflows 340
Motivation 340
Instance 341
Task 341
Challenge 342
What is Known 342
Extensions 342
Importance 342
6. Shortest Paths in Grids 343
Motivation 343
Instance 343
Task 345
Challenge 345
What is Known 345
Extensions 345
Importance 346
7. Sink Clustering 346
Motivation 346
Instance 348
Task 348
Challenge 348
What is Known 348
Extensions 349
Importance 349
8. Octagon Representation 350
Motivation 350
Instance 350
Task 350
Challenge 350
What is Known 350
Extensions 351
Importance 351
9. Short and Fast Fanout Trees 351
Motivation 351
Instance 352
Task 352
Challenge 352
What is Known 353
Extensions 353
Importance 354
10. Logic Synthesis 354
Motivation 354
Instance 354
Task 355
Challenge 355
What is Known 355
Extensions 355
Importance 356
Conclusion 356
References 356
Structural Properties of Sparse Graphs JAROSLAV NEŠETRIL* and PATRICE OSSONA DE MENDEZ* 361
Contents 361
1. Introduction 361
2. Measuring Sparsity 361
3. Sparse Classes of Graphs 361
4. Regular Partitions of Sparse Graphs 361
5. Algorithmic Applications 362
6. Homomorphisms and Logic 362
7. Summary (Characterization Theorems) 362
References 362
1. Introduction 362
1.1. Dense graphs 362
1.2. Sparse graphs 363
1.3. Nowhere dense graphs 365
2. Measuring Sparsity 365
2.1. Shallow minors and grads 366
2.2. Shallow topological minors and top-grads 368
2.3. Hajós or Hadwiger? 369
2.4. Stability with respect to lexicographic product 371
3. Sparse Classes of Graphs 372
3.1. Basic definitions 372
3.1.1. Limits. 372
3.1.2. Derived classes. 373
3.2. When is a class sparse or dense? 373
3.3. Within the nowhere dense world 375
3.4. Classes with bounded expansion 377
3.5. Proper minor closed classes 379
3.6. The full picture 380
4. Regular Partitions of Sparse Graphs 382
4.1. Tree-width 382
4.2. Tree-depth 382
4.3. Generalized coloring numbers 385
4.4. Low tree-width coloring 387
4.5. Low tree-depth coloring and p-centered colorings 388
4.6. Algorithmic considerations 390
4.6.1. Computing a Transitive Fraternal Augmentation. 391
5. Algorithmic Applications 392
5.1. Subgraph isomorphism problem 393
5.2. Small distance checking 394
5.3. Existential first-order properties 394
5.4. Dominating sets 395
5.5. Induced matchings 397
5.6. Vertex separators 398
6. Homomorphisms and Logic 399
6.1. Restricted dualities 399
6.2. Homomorphism preservation 402
6.3. Richness of first order 406
7. Summary (Characterization Theorems) 408
7.1. Polynomial dependence 408
7.2. Characterizations 409
7.2.1. Classes of nowhere dense graphs. 409
7.2.2. Bounded expansion classes. 410
7.2.3. Bounded tree-depth classes. 411
References 411
Recent Progress in Matching Extension MICHAEL D. PLUMMER 419
1. Introduction and a Brief History 419
2. n-extendability in General 421
3. Matching Extension in Embedded Graphs 425
4. Restricted Matching Extension: the E(m, n) Properties 428
5. Variations on a Theme 433
6. Bricks and Braces: a Brief Outline 434
7. Pfaffian Graphs 437
References 440
The Structure of the Complex of Maximal Lattice Free Bodies for a Matrix of Size (n + 1) × n HERBERT E. SCARF* 447
1. Introduction 447
2. Top 453
2.1. The Structure of Top. An Informal Presentation 457
3. Adjacent n Simplicies 461
4. Which k 1 Faces are Interior to Top? 462
5. Lattice Translates of Interior Simplicies 464
6. Intervals in Top [g] 465
7. Recovering Top from Top / Top [g] 470
7.1. Boundary Intervals in Top [g] 470
7.2. Interior Intervals in Top [g] 471
8. The Behavior of Top under Continuous Changes in a0 471
9. What is Next? 475
References 477
Graph Invariants in the Edge Model ALEXANDER SCHRIJVER 479
1. Introduction 479
2. The Characterization 480
3. Some Framework 481
4. Derivatives 483
5. Proof of Theorem 1 484
6. Derivation of Szegedy’s Theorem 488
7. Uniqueness of b 489
References 490
Incidences and the Spectra of Graphs* JÓZSEF SOLYMOSI† 491
1. Introduction 491
2. The Sum-Product Problem 492
2.1. The Sum-Product graph 493
2.2. The spectral bound 494
3. 3-term Arithmetic Progressions 495
4. Sidon functions 497
5. Incidence Bounds on Pseudolines 501
References 504
The Maturation of the Probabilistic Method JOEL SPENCER 506
1. Introduction 506
2. Common Elements 506
3. Lovász 508
4. Janson 511
References 514
A Structural Approach to Subset-Sum Problems VAN VU* 516
1. Introduction 516
2. Freiman’s Structural Theorem 520
3. Structure of Zero-Sum-Free Sets 521
3.1. The size of the largest zero-sum-free set in Zp 522
3.2. The structure of relatively large zero-sum-free sets 522
3.3. Erdos–Ginburg–Ziv revisited 523
4. Incomplete Sets 523
4.1. The structure of relatively large incomplete sets 524
4.2. The structure of incomplete sequences 525
4.3. Counting problems 526
5. Incomplete Sets in a General Abelian Group 526
6. Structures in SA 528
6.1. Folkman conjectures on infinite arithmetic progressions 529
6.2. Erdos conjecture on square-sum-free sets 530
7. Inverse Littlewood–Offord Theorems and Random Matrices 531
References 533

"Random Walks, Arrangements, Cell Complexes, Greedoids, and Self-organizing Libraries (p. 161-162)

ANDERS BJOERNER

To L´aszl´o Lov´asz on his 60th birthday The starting point is the known fact that some much-studied random walks on permutations, such as the Tsetlin library, arise from walks on real hyperplane arrangements. This paper explores similar walks on complex hyperplane arrangements. This is achieved by involving certain cell complexes naturally associated with the arrangement. In a particular case this leads to walks on libraries with several shelves. We also show that interval greedoids give rise to random walks belonging to the same general family. Members of this family of Markov chains, based on certain semigroups, have the property that all eigenvalues of the transition matrices are non-negative real and given by a simple combinatorial formula. Background material needed for understanding the walks is reviewed in rather great detail.

1. Introduction

The following random walk, called Tsetlin’s library, is a classic in the theory of combinatorial Markov chains. Consider books labeled by the integers 1, 2, . . . , n standing on a shelf in some order. A book is withdrawn according to some probability distribution w and then placed at the beginning of the shelf. Then another book is withdrawn according to w and placed at the beginning of the shelf, and so on. This Markov chain is of interest also for computer science, where it goes under names such as dynamic ?le management and cache management.

Much is known about the Tsetlin library, for instance good descriptions of its stationary distribution, good estimates of the rate of convergence to stationarity, exact formulas for the eigenvalues of its transition matrix Pw, and more. These eigenvalues are nonnegative real and their indexing and multiplicities, as well as their value, are given by very explicit combinatorial data. The Tsetlin library is the simplest of a class of Markov chains on permutations that can be described in terms of books on a shelf. Instead of one customer visiting the library to borrow one book which when returned is placed at the beginning of the shelf, we can picture several customers who each borrows several books. When the books are returned, the books of the ?rst borrower are placed at the beginning of the shelf in the induced order (i.e. the order they had before being borrowed).

Then the books of the second borrower are placed in their induced order, and so on. Finally, the remaining books that noone borrowed stand, in the induced order, at the end of the shelf. The analysis of such a “dynamic library” became part of a vastly more general theory through the work of Bidigare, Hanlon and Rockmore [2], continued and expanded by Brown and Diaconis [13, 14, 15, 16]. They created an attractive theory of random walks on hyperplane arrangements A in Rd, for which the states of the Markov chain are the regions making up the complement of ∪A in Rd. When adapted to the braid arrangement, whose regions are in bijective correspondence with the permutations of {1, 2, . . . , n}, their theory specializes precisely to the “self-organizing”, or “dynamic”, one-shelf library that we just described. The theory was later further generalized by Brown [13, 14] to a class of semigroups.

The genesis of this paper is the question: what about random walks on complex hyperplane arrangements? It is of course not at all clear what is meant. The complement in Cd of the union of a ?nite collection of hyperplanes is a 2d-dimensional manifold, so what determines a ?nite Markov chain? The idea is to consider not the complement itself, but rather a certain ?nite cell complex determining the complement up to homotopy type. In addition, we need that this complex extends to a cell complex for the whole singularity link, since much of the probability mass is typically placed in that extension. Such complexes were introduced by Ziegler and the author in [11]. The construction and basic properties partly run parallel to a similar construction in the real case, well-known from the theory of oriented matroids."