Building Bridges: Between Mathematics and Computer ScienceMartin Grötschel, Gyula O.H. Katona 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. |
Contents
| 9 | |
| 12 | |
| 15 | |
| 31 | |
Surplus of Graphs and the Lovász Local Lemma JÓZSEF BECK | 46 |
Deformable Polygon Representation and NearMincuts ANDRÁS A BENCZÚR and MICHEL X GOEMANS | 103 |
Variations for Lovsáz Submodular Ideas KRISTÓF BÉRCZI and ANDRÁS FRANK | 137 |
Random Walks Arrangements Cell Complexes Greedoids and Selforganizing Libraries ANDERS BJÖRNER | 165 |
Plünneckes Inequality for Different Summands KATALIN GYARMATI MÁTÉ MATOLCSI and IMRE Z RUZSA | 308 |
Decoupling and Partial Independence RAVI KANNAN | 321 |
Combinatorial Problems in Chip Design BERNHARD KORTE and JENS VYGEN | 333 |
Structural Properties of Sparse Graphs JAROSLAV NEŠETŘIL and PATRICE OSSONA DE MENDEZ | 369 |
Recent Progress in Matching Extension MICHAEL D PLUMMER | 427 |
The Structure of the Complex of Maximal Lattice Free Bodies for a Matrix of Size n + 1 n HERBERT E SCARF | 455 |
Graph Invariants in the Edge Model ALEXANDER SCHRIJVER | 487 |
Incidences and the Spectra of Graphs JÓZSEF SOLYMOSI | 499 |
The Finite Field Kakeya Problem AART BLOKHUIS and FRANCESCO MAZZOCCA | 204 |
An Abstract Szemerédi Regularity Lemma BÉLA BOLLOBÁS and VLADIMIR NIKIFOROV | 219 |
Isotropic PCA and AffineInvariant Clustering S CHARLES BRUBAKER and SANTOSH S VEMPALA | 241 |
Small Linear Dependencies for Binary Vectors of Low Weight URIEL FEIGE | 283 |
The Maturation of the Probabilistic Method JOEL SPENCER | 514 |
A Structural Approach to SubsetSum Problems VAN VU | 525 |