Grötschel / Katona Building Bridges

Between Mathematics and Computer Science
1. Auflage 2010
ISBN: 978-3-540-85221-6
Verlag: Springer-Verlag
Format: PDF
Kopierschutz: Wasserzeichen (»Systemvoraussetzungen)

E-Book, Englisch, 595 Seiten

Discrete mathematics and theoretical computer science are closely linked research areas with strong impacts on applications and various other scientific disciplines. Both fields deeply cross fertilize each other. One of the persons who particularly contributed to building bridges between these and many other areas is László Lovász, a scholar whose outstanding scientific work has defined and shaped many research directions in the last 40 years. A number of friends and colleagues, all top authorities in their fields of expertise and all invited plenary speakers at one of two conferences in August 2008 in Hungary, both celebrating Lovász's 60th birthday, have contributed their latest research papers to this volume. This collection of articles offers an excellent view on the state of combinatorics and related topics and will be of interest for experienced specialists as well as young researchers.

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

Autoren/Hrsg.

Grötschel, Martin

Katona, Gyula

Inhaltsverzeichnis

1;Title Page;4
2;Copyright Page;5
3;Table of Contents;6
4;Preface;8
5;Curriculum Vitae of László Lovász;11
6;Publications of László Lovász;14
6.1;Books:;14
6.2;Research papers:;15
6.3;Expository papers:;27
7;On the Power of Linear Dependencies IMRE BÁRÁNY;29
7.1;1. Introduction;29
7.2;2. The Steinitz lemma;30
7.3;3. The story of the Steinitz lemma;32
7.4;4. Signed sum;34
7.5;5. Signing vector sequences;36
7.6;6. Partitioning a sequence;39
7.7;7. A transference theorem;41
7.8;References;42
8;Surplus of Graphs and the Lovász Local Lemma JÓZSEF BECK ;44
8.1;1. What is the Surplus?;44
8.1.1;1. Row-Column Games.;44
8.1.2;2. Exact results.;47
8.1.3;3. The Core-Density and the Surplus.;50
8.1.4;4. Remarks.;53
8.1.5;5. Regular graphs – local randomness.;55
8.1.6;6. Can we use the Lovász Local Lemma in games?;56
8.1.7;7. When the Lovász Local Lemma successfully predicts the truth: examples in Tic-Tac-Toe like games.;58
8.1.8;8. How sharp is Theorem 1?;65
8.2;2. Potential Technique;67
8.2.1;1.;67
8.2.2;2.;70
8.2.3;3. Inevitable surplus is trivial.;73
8.2.4;4. Discrepancy and variance.;76
8.3;3. Proof of Theorem 1;80
8.3.1;1. What is the difficulty in general?;80
8.3.2;2. An alternative approach.;81
8.3.3;3. Global balancing.;85
8.3.4;4. An average argument.;89
8.4;4. Proof of Theorem 2: the Upper Bound;92
8.5;References;99
9;Deformable Polygon Representation and Near-Mincuts ANDRÁS A. BENCZÚR* and MICHEL X. GOEMANS† ;100
9.1;1. Introduction;100
9.2;2. Deformable Polygon Representation;103
9.3;3. Construction and its Proof;107
9.4;4. Mincuts and Near-Mincuts;122
9.5;5. Tree Hierarchy;124
9.6;6. Size of the Family;129
9.7;7. Conclusion;131
9.8;References;131
10;Variations for Lovsáz’ Submodular Ideas KRISTÓF BÉRCZI and ANDRÁS FRANK*;133
10.1;1. Introduction;133
10.2;2. Packing Arborescences;136
10.2.1;2.1. Basic cases;136
10.2.2;2.2. Extensions;140
10.3;3. Covering Supermodular Bi-set Functions by Digraphs;147
10.3.1;3.1. Simultaneous coverings;147
10.3.2;3.2. Applications to bipartite graphs and digraphs;154
10.3.3;3.3. Algorithmic aspects;156
10.4;References;158
11;Random Walks, Arrangements, Cell Complexes, Greedoids, and Self-organizing Libraries ANDERS BJÖRNER;161
11.1;1. Introduction;161
11.2;2. Real Hyperplane Arrangements;164
11.2.1;2.1. Basics;164
11.2.2;2.2. The braid arrangement;166
11.2.3;2.3. Cell complexes and zonotopes;168
11.2.4;2.4. The permutohedron and the k-equal arrangements;169
11.3;3. Complex Hyperplane Arrangements;172
11.3.1;3.1. Basics;172
11.3.2;3.2. Cell complexes;175
11.3.3;3.3. Complexified R-arrangements;176
11.4;4. Random Walks;178
11.4.1;4.1. Walks on semigroups;179
11.4.2;4.2. Walks on R-arrangements;181
11.4.3;4.3. Walks on C-arrangements;182
11.4.4;4.4. Walks on libraries;184
11.4.5;4.5. Walks on greedoids;189
11.5;5. Appendix;193
11.5.1;5.1. A generalized Zaslavsky formula;194
11.5.2;5.2. Lattice of intervals;195
11.5.3;5.3. Interval greedoids;196
11.6;References;198
12;The Finite Field Kakeya Problem AART BLOKHUIS and FRANCESCO MAZZOCCA;200
12.1;1. Introduction;200
12.2;2. Old and New Results in the Plane;201
12.3;3. Solution of Kakeya’s Problem in the Plane;204
12.4;4. Applications to Dual Blocking Sets;209
12.5;5. Old and New Results in Higher Dimensions;211
12.6;References;213
13;An Abstract Szemerédi Regularity Lemma BÉLA BOLLOBÁS* and VLADIMIR NIKIFOROV;214
13.1;1. Introduction;214
13.1.1;1.1. Measure triples;215
13.1.2;1.2. SR-systems;216
13.1.2.1;1.2.1. Using SR-systems to define e-regularity.;217
13.1.3;1.3. Partitions in measure triples;219
13.1.3.1;1.3.1. Bounding families of partitions.;219
13.2;2. The main result;219
13.3;3. Applications;220
13.3.1;3.1. Equitable partitions;220
13.3.2;3.2. Regularity lemmas for k-graphs;221
13.3.2.1;3.2.1. A regularity lemma for k-partite k-graphs.;222
13.3.3;3.3. Regularity lemmas for the cube [0, 1]k;222
13.3.4;3.4. Regularity lemmas for functions and matrices;223
13.3.4.1;3.4.1. A regularity lemma for matrices.;224
13.4;4. Proofs;225
13.4.1;4.1. Proof of Theorem 13;226
13.4.2;4.2. Proof of Lemma 14;231
13.4.3;4.3. Proof of Theorem 23;232
13.5;References;234
14;Isotropic PCA and Affine-Invariant Clustering S. CHARLES BRUBAKER and SANTOSH S. VEMPALA;236
14.1;1. Introduction;236
14.1.1;1.1. Previous work;238
14.1.2;1.2. Results;241
14.2;2. Algorithm;245
14.2.1;2.1. Parallel pancakes;246
14.2.2;2.2. Overview of analysis;247
14.3;3. Preliminaries;247
14.3.1;3.1. Matrix properties;247
14.3.2;3.2. The Fisher criterion and isotropy;249
14.3.3;3.3. Approximation of the reweighted moments;252
14.3.3.1;3.3.1. Single Component.;252
14.3.3.2;3.3.2. Mixture moments.;255
14.3.4;3.4. Sample convergence;259
14.3.5;3.5. Perturbation lemma;262
14.4;4. Finding a Vector near the Fisher Subspace;262
14.4.1;4.1. Mean shift;264
14.4.2;4.2. Spectral method;265
14.5;5. Recursion;270
14.6;6. Conclusion;275
14.7;References;275
15;Small Linear Dependencies for Binary Vectors of Low Weight URIEL FEIGE;277
15.1;1. Introduction;277
15.1.1;1.1. Motivation and related work;280
15.2;2. Distinguished Cycles Shorter than log n;282
15.3;3. Distinguished Cycles Longer than log n;288
15.3.1;3.1. A digression;289
15.3.2;3.2. Back to the main proof;291
15.3.3;3.3. A negative example;295
15.3.4;3.4. Extensions;296
15.4;4. Nontrivial Cycles of Length O(log n);298
15.5;References;301
16;Plünnecke’s Inequality for Different Summands KATALIN GYARMATI*, MÁTÉ MATOLCSI† and IMRE Z. RUZSA‡;302
16.1;1. Introduction;302
16.2;2. The Case k = l + 1;305
16.3;3. The General Case;307
16.4;4. Removing the Constant;309
16.5;5. Finding a Large Subset;309
16.6;6. An Application to Restricted Sums;311
16.7;References;313
17;Decoupling and Partial Independence RAVI KANNAN;314
17.1;1. Introduction;314
17.2;2. Proof of the Square-form Theorem;317
17.2.1;2.1. Decoupling;319
17.3;3. Proof of Theorems 2 and 3;321
17.4;References;323
18;Combinatorial Problems in Chip Design BERNHARD KORTE and JENS VYGEN;325
18.1;Introduction;325
18.2;1. Floorplanning;328
18.2.1;Motivation;328
18.2.2;Instance;328
18.2.3;Task;329
18.2.4;Challenge;329
18.2.5;What is Known;329
18.2.6;Extensions;330
18.2.7;Importance;331
18.3;2. Lower Bounds for Placement;331
18.3.1;Motivation;331
18.3.2;Instance;332
18.3.3;Task;332
18.3.4;Challenge;332
18.3.5;What is Known;332
18.3.6;Extensions;334
18.3.7;Importance;335
18.4;3. Legalizing a Placement;335
18.4.1;Motivation;335
18.4.2;Instance;335
18.4.3;Task;335
18.4.4;Challenge;336
18.4.5;What is Known;336
18.4.6;Extensions;336
18.4.7;Importance;337
18.5;4. Steiner Trees Minimizing Elmore Delay;337
18.5.1;Motivation;337
18.5.2;Instance;338
18.5.3;Task;338
18.5.4;Challenge;339
18.5.5;What is Known;339
18.5.6;Extensions;339
18.5.7;Importance;340
18.6;5. Resource Sharing and Multiflows;340
18.6.1;Motivation;340
18.6.2;Instance;341
18.6.3;Task;341
18.6.4;Challenge;342
18.6.5;What is Known;342
18.6.6;Extensions;342
18.6.7;Importance;342
18.7;6. Shortest Paths in Grids;343
18.7.1;Motivation;343
18.7.2;Instance;343
18.7.3;Task;345
18.7.4;Challenge;345
18.7.5;What is Known;345
18.7.6;Extensions;345
18.7.7;Importance;346
18.8;7. Sink Clustering;346
18.8.1;Motivation;346
18.8.2;Instance;348
18.8.3;Task;348
18.8.4;Challenge;348
18.8.5;What is Known;348
18.8.6;Extensions;349
18.8.7;Importance;349
18.9;8. Octagon Representation;350
18.9.1;Motivation;350
18.9.2;Instance;350
18.9.3;Task;350
18.9.4;Challenge;350
18.9.5;What is Known;350
18.9.6;Extensions;351
18.9.7;Importance;351
18.10;9. Short and Fast Fanout Trees;351
18.10.1;Motivation;351
18.10.2;Instance;352
18.10.3;Task;352
18.10.4;Challenge;352
18.10.5;What is Known;353
18.10.6;Extensions;353
18.10.7;Importance;354
18.11;10. Logic Synthesis;354
18.11.1;Motivation;354
18.11.2;Instance;354
18.11.3;Task;355
18.11.4;Challenge;355
18.11.5;What is Known;355
18.11.6;Extensions;355
18.11.7;Importance;356
18.12;Conclusion;356
18.13;References;356
19;Structural Properties of Sparse Graphs JAROSLAV NEŠETRIL* and PATRICE OSSONA DE MENDEZ*;361
19.1;Contents;361
19.1.1;1. Introduction;361
19.1.2;2. Measuring Sparsity;361
19.1.3;3. Sparse Classes of Graphs;361
19.1.4;4. Regular Partitions of Sparse Graphs;361
19.1.5;5. Algorithmic Applications;362
19.1.6;6. Homomorphisms and Logic;362
19.1.7;7. Summary (Characterization Theorems);362
19.1.8;References;362
19.2;1. Introduction;362
19.2.1;1.1. Dense graphs;362
19.2.2;1.2. Sparse graphs;363
19.2.3;1.3. Nowhere dense graphs;365
19.3;2. Measuring Sparsity;365
19.3.1;2.1. Shallow minors and grads;366
19.3.2;2.2. Shallow topological minors and top-grads;368
19.3.3;2.3. Hajós or Hadwiger?;369
19.3.4;2.4. Stability with respect to lexicographic product;371
19.4;3. Sparse Classes of Graphs;372
19.4.1;3.1. Basic definitions;372
19.4.1.1;3.1.1. Limits.;372
19.4.1.2;3.1.2. Derived classes.;373
19.4.2;3.2. When is a class sparse or dense?;373
19.4.3;3.3. Within the nowhere dense world;375
19.4.4;3.4. Classes with bounded expansion;377
19.4.5;3.5. Proper minor closed classes;379
19.4.6;3.6. The full picture;380
19.5;4. Regular Partitions of Sparse Graphs;382
19.5.1;4.1. Tree-width;382
19.5.2;4.2. Tree-depth;382
19.5.3;4.3. Generalized coloring numbers;385
19.5.4;4.4. Low tree-width coloring;387
19.5.5;4.5. Low tree-depth coloring and p-centered colorings;388
19.5.6;4.6. Algorithmic considerations;390
19.5.6.1;4.6.1. Computing a Transitive Fraternal Augmentation.;391
19.6;5. Algorithmic Applications;392
19.6.1;5.1. Subgraph isomorphism problem;393
19.6.2;5.2. Small distance checking;394
19.6.3;5.3. Existential first-order properties;394
19.6.4;5.4. Dominating sets;395
19.6.5;5.5. Induced matchings;397
19.6.6;5.6. Vertex separators;398
19.7;6. Homomorphisms and Logic;399
19.7.1;6.1. Restricted dualities;399
19.7.2;6.2. Homomorphism preservation;402
19.7.3;6.3. Richness of first order;406
19.8;7. Summary (Characterization Theorems);408
19.8.1;7.1. Polynomial dependence;408
19.8.2;7.2. Characterizations;409
19.8.2.1;7.2.1. Classes of nowhere dense graphs.;409
19.8.2.2;7.2.2. Bounded expansion classes.;410
19.8.2.3;7.2.3. Bounded tree-depth classes.;411
19.9;References;411
20;Recent Progress in Matching Extension MICHAEL D. PLUMMER;419
20.1;1. Introduction and a Brief History;419
20.2;2. n-extendability in General;421
20.3;3. Matching Extension in Embedded Graphs;425
20.4;4. Restricted Matching Extension: the E(m, n) Properties;428
20.5;5. Variations on a Theme;433
20.6;6. Bricks and Braces: a Brief Outline;434
20.7;7. Pfaffian Graphs;437
20.8;References;440
21;The Structure of the Complex of Maximal Lattice Free Bodies for a Matrix of Size (n + 1) × n HERBERT E. SCARF*;447
21.1;1. Introduction;447
21.2;2. Top;453
21.2.1;2.1. The Structure of Top. An Informal Presentation;457
21.3;3. Adjacent n Simplicies;461
21.4;4. Which k 1 Faces are Interior to Top?;462
21.5;5. Lattice Translates of Interior Simplicies;464
21.6;6. Intervals in Top [g];465
21.7;7. Recovering Top from Top / Top [g];470
21.7.1;7.1. Boundary Intervals in Top [g];470
21.7.2;7.2. Interior Intervals in Top [g];471
21.8;8. The Behavior of Top under Continuous Changes in a0;471
21.9;9. What is Next?;475
21.10;References;477
22;Graph Invariants in the Edge Model ALEXANDER SCHRIJVER;479
22.1;1. Introduction;479
22.2;2. The Characterization;480
22.3;3. Some Framework;481
22.4;4. Derivatives;483
22.5;5. Proof of Theorem 1;484
22.6;6. Derivation of Szegedy’s Theorem;488
22.7;7. Uniqueness of b;489
22.8;References;490
23;Incidences and the Spectra of Graphs* JÓZSEF SOLYMOSI†;491
23.1;1. Introduction;491
23.2;2. The Sum-Product Problem;492
23.2.1;2.1. The Sum-Product graph;493
23.2.2;2.2. The spectral bound;494
23.3;3. 3-term Arithmetic Progressions;495
23.4;4. Sidon functions;497
23.5;5. Incidence Bounds on Pseudolines;501
23.6;References;504
24;The Maturation of the Probabilistic Method JOEL SPENCER;506
24.1;1. Introduction;506
24.2;2. Common Elements;506
24.3;3. Lovász;508
24.4;4. Janson;511
24.5;References;514
25;A Structural Approach to Subset-Sum Problems VAN VU*;516
25.1;1. Introduction;516
25.2;2. Freiman’s Structural Theorem;520
25.3;3. Structure of Zero-Sum-Free Sets;521
25.3.1;3.1. The size of the largest zero-sum-free set in Zp;522
25.3.2;3.2. The structure of relatively large zero-sum-free sets;522
25.3.3;3.3. Erdos–Ginburg–Ziv revisited;523
25.4;4. Incomplete Sets;523
25.4.1;4.1. The structure of relatively large incomplete sets;524
25.4.2;4.2. The structure of incomplete sequences;525
25.4.3;4.3. Counting problems;526
25.5;5. Incomplete Sets in a General Abelian Group;526
25.6;6. Structures in SA;528
25.6.1;6.1. Folkman conjectures on infinite arithmetic progressions;529
25.6.2;6.2. Erdos conjecture on square-sum-free sets;530
25.7;7. Inverse Littlewood–Offord Theorems and Random Matrices;531
25.8;References;533

Leseproben

"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."