Издательство Springer, 2010, -366 pp.
This book is the second volume of mathematical papers to commemorate the 60th birthday of Laszlo ('Laci') Lovasz on March 9, 2008. Prominent mathematicians that were inspired by Laci were invited to contribute to the celebrations of this milestone in the Summer of 2008. The response was overwhelming, and therefore two conferences were organized , the first from 5-9 August 2008 in Budapest, and the second the week after, from 11-15 August 2008 in Keszthely, at the borders of Lake Balaton. The first meeting was baptized Building Bridges - Between Mathematics and Computer Science, the second Fete of Combinatorics and Computer Science. These names also ado the two volumes published to commemorate the celebrations.
The two names very well reflect the power and the beauty of Laci's work. Many of his results indeed can be characterized by building new, powerful bridges between and within mathematics and computer science, and these are really feasts to the combinatorial and algorithmic mind. Several of the methods found by Lovasz have opened up new areas of research in discrete mathematics and algorithmics. Often, these methods were obtained by Lovasz by developing beautiful new techniques based on algebra , geometry, or topology, thus laying fundaments for the important role of classical mathematics in more mode fields like combinatorics, optimization, algorithmics, and complexity.
Laci Lovasz has obtained so many pioneering results that it would be quite impossible to describe a reasonable part of it . Let us just give a brief selection. He solved several important open problems in discrete mathematics, like the perfect graph conjecture, Kneser's conjecture, the Shannon capacity problem , the matroid matching problem, and the matching lattice problem. He proved the now called 'Lovasz Local Lemma', basic in probabilistic combinatorics and randomized algorithms. He pointed out the significance of the ellipsoid method and semidefinite programming for combinatorial optimization, and he designed the lattice basis reduction method, with a wealth of applications in discrete mathematics, combinatorial optimization , integer programming, number theory, algebra, and cryptography. Other basic algorithmic results were found for volume computation and communication complexity. Recently, Laci was the main inspirator of the new area of graph limits, with its connections to extremal combinatorics and mathematical physics.
Laci's deep insight in the combinatorial and algorithmic potentials of geometry and topology is unique. Several of his results are ground-breaking, and there seems little chance that they would have been detected without him. They have inspired and directed the work of a huge part of the researchers in discrete mathematics, optimization, and algorithmics. Laci's reputation is beyond any measure not only because of his results and insights , but also because of his very pleasant modesty, his willingness to cooperate and to exchange ideas, and the extreme transparency of his lectures, which form usually exciting eye-openers. The inspiration and charismatic ambiance offered by Laci and his wife Kati have given them many friends and collaborators, all over the world and in a wide range in mathematics and computer science. We are very happy that many of them have reacted enthusiastically to our invitation to contribute to the volumes, and that we received so many excellent articles. Like the first volume, also this second volume forms an expression of the impact of Laci Lovasz's work and of the inspiration given by him to many scientists world-wide.
Preface.
High Degree Graphs Contain Large-Star Factors.
Iterated Triangle Partitions.
PageRank and Random Walks on Graphs.
Solution of Peter Winkler's Pizza Problem.
Tight Bounds for Embedding Bounded Degree Trees.
Betti Numbers are Testable.
Rigid and Globally Rigid Graphs with Pinned Vertices.
Noise Sensitivity and Chaos in Social Choice Theory.
Coloring Uniform Hypergraphs with Small Edge Degrees.
Extremal Graphs and Multigraphs with Two Weighted Colours.
Regularity Lemmas for Graphs.
Edge Coloring Models as Singular Vertex Coloring Models.
List Total Weighting of Graphs.
Open problems.
This book is the second volume of mathematical papers to commemorate the 60th birthday of Laszlo ('Laci') Lovasz on March 9, 2008. Prominent mathematicians that were inspired by Laci were invited to contribute to the celebrations of this milestone in the Summer of 2008. The response was overwhelming, and therefore two conferences were organized , the first from 5-9 August 2008 in Budapest, and the second the week after, from 11-15 August 2008 in Keszthely, at the borders of Lake Balaton. The first meeting was baptized Building Bridges - Between Mathematics and Computer Science, the second Fete of Combinatorics and Computer Science. These names also ado the two volumes published to commemorate the celebrations.
The two names very well reflect the power and the beauty of Laci's work. Many of his results indeed can be characterized by building new, powerful bridges between and within mathematics and computer science, and these are really feasts to the combinatorial and algorithmic mind. Several of the methods found by Lovasz have opened up new areas of research in discrete mathematics and algorithmics. Often, these methods were obtained by Lovasz by developing beautiful new techniques based on algebra , geometry, or topology, thus laying fundaments for the important role of classical mathematics in more mode fields like combinatorics, optimization, algorithmics, and complexity.
Laci Lovasz has obtained so many pioneering results that it would be quite impossible to describe a reasonable part of it . Let us just give a brief selection. He solved several important open problems in discrete mathematics, like the perfect graph conjecture, Kneser's conjecture, the Shannon capacity problem , the matroid matching problem, and the matching lattice problem. He proved the now called 'Lovasz Local Lemma', basic in probabilistic combinatorics and randomized algorithms. He pointed out the significance of the ellipsoid method and semidefinite programming for combinatorial optimization, and he designed the lattice basis reduction method, with a wealth of applications in discrete mathematics, combinatorial optimization , integer programming, number theory, algebra, and cryptography. Other basic algorithmic results were found for volume computation and communication complexity. Recently, Laci was the main inspirator of the new area of graph limits, with its connections to extremal combinatorics and mathematical physics.
Laci's deep insight in the combinatorial and algorithmic potentials of geometry and topology is unique. Several of his results are ground-breaking, and there seems little chance that they would have been detected without him. They have inspired and directed the work of a huge part of the researchers in discrete mathematics, optimization, and algorithmics. Laci's reputation is beyond any measure not only because of his results and insights , but also because of his very pleasant modesty, his willingness to cooperate and to exchange ideas, and the extreme transparency of his lectures, which form usually exciting eye-openers. The inspiration and charismatic ambiance offered by Laci and his wife Kati have given them many friends and collaborators, all over the world and in a wide range in mathematics and computer science. We are very happy that many of them have reacted enthusiastically to our invitation to contribute to the volumes, and that we received so many excellent articles. Like the first volume, also this second volume forms an expression of the impact of Laci Lovasz's work and of the inspiration given by him to many scientists world-wide.
Preface.
High Degree Graphs Contain Large-Star Factors.
Iterated Triangle Partitions.
PageRank and Random Walks on Graphs.
Solution of Peter Winkler's Pizza Problem.
Tight Bounds for Embedding Bounded Degree Trees.
Betti Numbers are Testable.
Rigid and Globally Rigid Graphs with Pinned Vertices.
Noise Sensitivity and Chaos in Social Choice Theory.
Coloring Uniform Hypergraphs with Small Edge Degrees.
Extremal Graphs and Multigraphs with Two Weighted Colours.
Regularity Lemmas for Graphs.
Edge Coloring Models as Singular Vertex Coloring Models.
List Total Weighting of Graphs.
Open problems.