Building Bridges

by Grotschel, Martin; Katona, Gyula O. H.

• ISBN13: 9783540852186
• ISBN10: 3540852182
• Format: Hardcover
• Copyright: 2008-11-11
• Publisher: Springer Verlag

Summary

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.

Author Biography

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

Table of Contents

Curriculum vitae of Laszlo Lovasz	p. 11
Publications of Laszlo Lovasz	p. 15
On the power of linear dependencies	p. 31
Surplus of graphs and the Lovasz local lemma	p. 47
Deformable polygon representation and near-mincuts	p. 103
Variations for Lovasz' submodular ideas	p. 137
Random walks, arrangements, cell complexes, greedoids, and self-organizing libraries	p. 165
The finite field Kakeya problem	p. 205
An abstract Szemeredi regularity lemma	p. 219
Isotropic PCA and affine-invariant clustering	p. 241
Small linear dependencies for binary vectors of low weight	p. 283
Plunnecke's inequality for different summands	p. 309
Decoupling and partial independence	p. 321
Combinatorial problems in chip design	p. 333
Structural properties of sparse graphs	p. 369
Recent progress in matching extension	p. 427
The structure of the complex of maximal lattice free bodies for a matrix of size (n + 1) x n	p. 455
Graph invariants in the edge model	p. 487
Incidences and the spectra of graphs	p. 499
The maturation of the probabilistic method	p. 515
A structural approach to subset-sum problems	p. 525
Table of Contents provided by Blackwell. All Rights Reserved.