Grötschel M., Katona G. (eds.) Building Bridges. Between Mathematics and Computer Science

Springer; János Bolyai Mathematical Society (Budapest), 2008. — 535 p. — (Bolyai Society Mathematical Studies 19). — ISBN 3-540-85218-6, 978-963-9453-11-1.László Lovász, briefly called Laci by his friends, turned sixty on March 9, 2008. To celebrate this special birthday two conferences have been held in Hungary, one in Budapest (August 5–9, 2008) with invited speakers only and one in Keszthely (August 11–15, 2008). Several top mathematicians and computer scientists have not only lectured at these meetings but also dedicated (together with some coauthors) research papers to this occasion. This volume is the collection of their articles. The contributions to the conferences and this book honor a person who has not only made an almost uncountable number of fundamental contributions to mathematics and computer science, but who also broke down many borders between mathematical disciplines and built sustainable bridges between mathematics and computer science.
Laci has been a role model for many young researchers, he inspired lots of colleagues, and guided quite a few scientific careers. In addition, he is an extremely nice person and very pleasant colleague, and that is why so many researchers have come to the Lovasz meetings in Hungary to present their best recent work and celebrate with him.
In the Fazekas Mihaly Gimn´azium in Budapest, a breeding place of world class mathematicians, Laci’s outstanding talent became visible at very young age. He did not only win various mathematics competitions in Hungary, Lovasz also won three gold medals and one silver medal in the International Mathematical Olympiad. The solution of an open problem in lattice theory gained him his first international visibility and soon after, in 1972, his proof of the perfect graph theorem earned him lasting fame in graph theory. An unparalleled sequence of scientific achievements followed and is continuing till today. It is impossible to mention even a small fraction of Laci’s results here. The list of his publications (up to summer 2008) is contained in this volume to indicate the breadth and depth of his contributions.
Being a combinatorialist at heart, like so many Hungarian mathematicians, it has been natural for Laci to employ combinatorial techniques in other areas of mathematics; but he also brought topology, algebra, analysis, stochastics and other mathematical fields to combinatorics, often in quite unusual ways. In this way he opened up quite a number of new flourishing fields of research. Algorithmic issues such as polynomial time solvability and general complexity theory opened his eyes for computer science where he particularly contributed to the interface between computer science and discrete mathematics.Curriculum Vitae of László Lovász
Publications of László Lovász
On the Power of Linear Dependencies
Surplus of Graphs and the Lovasz Local Lemma
Deformable Polygon Representation and Near-Mincuts
Variations for Lovasz Submodular Ideas
Random Walks, Arrangements, Cell Complexes, Greedoids, and Self-organizing Libraries
The Finite Field Kakeya Problem
An Abstract Szemeredi Regularity Lemma
Isotropic PCA and Affine-Invariant Clustering
Small Linear Dependencies for Binary Vectors of Low Weight
Plunnecke’s Inequality for Different Summands
Decoupling and Partial Independence
Combinatorial Problems in Chip Design
Structural Properties of Sparse Graphs
Recent Progress in Matching Extension
Structure of the Complex of Maximal Lattice Free Bodies for a Matrix of Size (n+1)×n
Graph Invariants in the Edge Model
Incidences and the Spectra of Graphs
The Maturation of the Probabilistic Method
A Structural Approach to Subset-Sum Problems