László Lovász - Böcker

Discrete mathematics is quickly becoming one of the most important areas of mathematical research, with applications to cryptography, linear programming, coding theory and the theory of computing. This book is aimed at undergraduate mathematics and computer science students interested in developing a feeling for what mathematics is all about, where mathematics can be helpful, and what kinds of questions mathematicians work on. The authors discuss a number of selected results and methods of discrete mathematics, mostly from the areas of combinatorics and graph theory, with a little number theory, probability, and combinatorial geometry. Wherever possible, the authors use proofs and problem solving to help students understand the solutions to problems. In addition, there are numerous examples, figures and exercises spread throughout the book. Laszlo Lovasz is a Senior Researcher in the Theory Group at Microsoft Corporation. He is a recipient of the 1999 Wolf Prize andthe Godel Prize for the top paper in Computer Science. Jozsef Pelikan is Professor of Mathematics in the Department of Algebra and Number Theory at Eotvos Lorand University, Hungary. In 2002, he was elected Chairman of the Advisory Board of the International Mathematical Olympiad. Katalin Vesztergombi is Senior Lecturer in the Department of Mathematics at the University of Washington.

Discrete mathematics is quickly becoming one of the most important areas of mathematical research, with applications to cryptography, linear programming, coding theory and the theory of computing. This book is aimed at undergraduate mathematics and computer science students interested in developing a feeling for what mathematics is all about, where mathematics can be helpful, and what kinds of questions mathematicians work on. The authors discuss a number of selected results and methods of discrete mathematics, mostly from the areas of combinatorics and graph theory, with a little number theory, probability, and combinatorial geometry. Wherever possible, the authors use proofs and problem solving to help students understand the solutions to problems. In addition, there are numerous examples, figures and exercises spread throughout the book. Laszlo Lovasz is a Senior Researcher in the Theory Group at Microsoft Corporation. He is a recipient of the 1999 Wolf Prize andthe Godel Prize for the top paper in Computer Science. Jozsef Pelikan is Professor of Mathematics in the Department of Algebra and Number Theory at Eotvos Lorand University, Hungary. In 2002, he was elected Chairman of the Advisory Board of the International Mathematical Olympiad. Katalin Vesztergombi is Senior Lecturer in the Department of Mathematics at the University of Washington.

The main purpose of this book is to provide help in learning existing techniques in combinatorics. The most effective way of learning such techniques is to solve exercises and problems. This book presents all the material in the form of problems and series of problems (apart from some general comments at the beginning of each chapter). In the second part, a hint is given for each exercise, which contains the main idea necessary for the solution, but allows the reader to practice the techniques by completing the proof. In the third part, a full solution is provided for each problem. This book will be useful to those students who intend to start research in graph theory, combinatorics or their applications, and for those researchers who feel that combinatorial techniques might help them with their work in other branches of mathematics, computer science, management science, electrical engineering and so on. For background, only the elements of linear algebra, group theory, probability and calculus are needed.

Recently, it became apparent that a large number of the most interesting structures and phenomena of the world can be described by networks. To develop a mathematical theory of very large networks is an important challenge. This book describes one recent approach to this theory, the limit theory of graphs, which has emerged over the last decade. The theory has rich connections with other approaches to the study of large networks, such as ``property testing'' in computer science and regularity partition in graph theory. It has several applications in extremal graph theory, including the exact formulations and partial answers to very general questions, such as which problems in extremal graph theory are decidable. It also has less obvious connections with other parts of mathematics (classical and non-classical, like probability theory, measure theory, tensor algebras, and semidefinite optimization). This book explains many of these connections, first at an informal level to emphasize the need to apply more advanced mathematical methods, and then gives an exact development of the theory of the algebraic theory of graph homomorphisms and of the analytic theory of graph limits. This is an amazing book: readable, deep, and lively. It sets out this emerging area, makes connections between old classical graph theory and graph limits, and charts the course of the future. --Persi Diaconis, Stanford University This book is a comprehensive study of the active topic of graph limits and an updated account of its present status. It is a beautiful volume written by an outstanding mathematician who is also a great expositor. --Noga Alon, Tel Aviv University, Israel Modern combinatorics is by no means an isolated subject in mathematics, but has many rich and interesting connections to almost every area of mathematics and computer science. The research presented in Lovasz's book exemplifies this phenomenon. This book presents a wonderful opportunity for a student in combinatorics to explore other fields of mathematics, or conversely for experts in other areas of mathematics to become acquainted with some aspects of graph theory. --Terence Tao, University of California, Los Angeles, CA Laszlo Lovasz has written an admirable treatise on the exciting new theory of graph limits and graph homomorphisms, an area of great importance in the study of large networks. It is an authoritative, masterful text that reflects Lovasz's position as the main architect of this rapidly developing theory. The book is a must for combinatorialists, network theorists, and theoretical computer scientists alike. --Bela Bollobas, Cambridge University, UK

Graphs are usually represented as geometric objects drawn in the plane, consisting of nodes and curves connecting them. The main message of this book is that such a representation is not merely a way to visualize the graph, but an important mathematical tool. It is obvious that this geometry is crucial in engineering, for example, if you want to understand rigidity of frameworks and mobility of mechanisms. But even if there is no geometry directly connected to the graph-theoretic problem, a well-chosen geometric embedding has mathematical meaning and applications in proofs and algorithms. This book surveys a number of such connections between graph theory and geometry: among others, rubber band representations, coin representations, orthogonal representations, and discrete analytic functions. Applications are given in information theory, statistical physics, graph algorithms and quantum physics. The book is based on courses and lectures that the author has given over the last few decades and offers readers with some knowledge of graph theory, linear algebra, and probability a thorough introduction to this exciting new area with a large collection of illuminating examples and exercises.

Die diskrete Mathematik ist im Begriff, zu einem der wichtigsten Gebiete der mathematischen Forschung zu werden mit Anwendungen in der Kryptographie, der linearen Programmierung, der Kodierungstheorie und Informatik. Dieses Buch richtet sich an Studenten der Mathematik und Informatik, die ein Gefühl dafür entwickeln möchten, worum es in der Mathematik geht, wobei Mathematik hilfreich sein kann, und mit welcher Art Fragen sich Mathematiker auseinandersetzen.Die Autoren stellen eine Anzahl ausgewählter Ergebnisse und Methoden der diskreten Mathematik vor, hauptsächlich aus den Bereichen Kombinatorik und Graphentheorie, teilweise aber auch aus der Zahlentheorie, der Wahrscheinlichkeitsrechnung und der kombinatorischen Geometrie.Wo immer es möglich war, haben die Autoren Beweise und Problemlösungen verwendet, um den Studenten zu helfen, die Lösungen der Fragestellungen zu verstehen.Zusätzlich ist eine Vielzahl von Beispielen, Bildern und Übungsaufgaben über das Buch verteilt.László Lovász ist einer der Leiter der theoretischen Forschungsabteilung der Microsoft Corporation. Er hat 1999 den Wolf-Preis sowie den Gödel-Preis für die beste wissenschaftliche Veröffentlichung in der Informatik erhalten. József Pelikán ist Professor am Institut für Algebra und Zahlentheorie der Eötvös Loránd Universität in Budapest.  Katalin Vesztergombi ist Senior Lecturer am Fachbereich Mathematik der Universität von Washington in Seattle.

Discrete mathematics, including (combinatorial) number theory and set theory has always been a stronghold of Hungarian mathematics. The present volume honouring Vera Sos and Andras Hajnal contains survey articles (with classical theorems and state-of-the-art results) and cutting edge expository research papers with new theorems and proofs in the area of the classical Hungarian subjects, like extremal combinatorics, colorings, combinatorial number theory, etc. The open problems and the latest results in the papers inspire further research. The volume is recommended to experienced specialists as well as to young researchers and students.

Since his death in 1996, many scientific meetings have been dedicated to the memory of Paul Erdös. From July 4 to 11, 1999, the conference "Paul Erdös and his Mathematics" was held in Budapest, with the ambitious goal of showing the whole range of Erdös' work - a difficult task in view of Erdös' versatility and his broad scope of interest in mathematics. According to this goal, the topics of lectures, given by the leading specialists of the subjects, included number theory, combinatorics, analysis, set theory, probability, geometry and areas connecting them, like ergodic theory. The conference has contributed to changing the common view that Erdös worked only in combinatorics and combinatorial number theory. In the present two volumes, the editors have collected, besides some personal reminiscences by Paul's old friends, mainly survey articles on his work, and on areas he initiated or worked in.

The editors and authors dedicate this book to Bernhard Korte on the occasion of his seventieth birthday. We, the editors, are happy about the overwhelming feedback to our initiative to honor him with this book and with a workshop in Bonn on November 3–7,2008.Althoughthiswouldbeareasontolookback,wewouldratherliketolook forward and see what are the interesting research directions today. This book is written by leading experts in combinatorial optimization. All - pers were carefully reviewed, and eventually twenty-three of the invited papers were accepted for this book. The breadth of topics is typical for the eld: combinatorial optimization builds bridges between areas like combinatorics and graph theory, submodular functions and matroids, network ows and connectivity, approximation algorithms and mat- matical programming, computational geometry and polyhedral combinatorics. All these topics are related, and they are all addressed in this book. Combi- torial optimization is also known for its numerous applications. To limit the scope, however, this book is not primarily about applications, although some are mentioned at various places. Most papers in this volume are surveys that provide an excellent overview of an activeresearcharea,butthisbookalsocontainsmanynewresults.Highlightingmany of the currently most interesting research directions in combinatorial optimization, we hope that this book constitutes a good basis for future research in these areas.

Hungarian mathematics has always been known for discrete mathematics, including combinatorial number theory, set theory and recently random structures, combinatorial geometry as well. The recent volume contains high level surveys on these topics with authors mostly being invited speakers for the conference "Horizons of Combinatorics" held in Balatonalmadi, Hungary in 2006. The collection gives a very good overview of recent trends and results in a large part of combinatorics and related topics, and offers an interesting reading for experienced specialists as well as to young researchers and students.

The editors and authors dedicate this book to Bernhard Korte on the occasion of his seventieth birthday. We, the editors, are happy about the overwhelming feedback to our initiative to honor him with this book and with a workshop in Bonn on November 3–7,2008.Althoughthiswouldbeareasontolookback,wewouldratherliketolook forward and see what are the interesting research directions today. This book is written by leading experts in combinatorial optimization. All - pers were carefully reviewed, and eventually twenty-three of the invited papers were accepted for this book. The breadth of topics is typical for the eld: combinatorial optimization builds bridges between areas like combinatorics and graph theory, submodular functions and matroids, network ows and connectivity, approximation algorithms and mat- matical programming, computational geometry and polyhedral combinatorics. All these topics are related, and they are all addressed in this book. Combi- torial optimization is also known for its numerous applications. To limit the scope, however, this book is not primarily about applications, although some are mentioned at various places. Most papers in this volume are surveys that provide an excellent overview of an activeresearcharea,butthisbookalsocontainsmanynewresults.Highlightingmany of the currently most interesting research directions in combinatorial optimization, we hope that this book constitutes a good basis for future research in these areas.

Hungarian mathematics has always been known for discrete mathematics, including combinatorial number theory, set theory and recently random structures, combinatorial geometry as well. The recent volume contains high level surveys on these topics with authors mostly being invited speakers for the conference "Horizons of Combinatorics" held in Balatonalmadi, Hungary in 2006. The collection gives a very good overview of recent trends and results in a large part of combinatorics and related topics, and offers an interesting reading for experienced specialists as well as to young researchers and students.

Paul Erdös was one of the most influential mathematicians of the twentieth century, whose work in number theory, combinatorics, set theory, analysis, and other branches of mathematics has determined the development of large areas of these fields.

Discrete mathematics, including (combinatorial) number theory and set theory has always been a stronghold of Hungarian mathematics. The present volume honouring Vera Sos and Andras Hajnal contains survey articles (with classical theorems and state-of-the-art results) and cutting edge expository research papers with new theorems and proofs in the area of the classical Hungarian subjects, like extremal combinatorics, colorings, combinatorial number theory, etc. The open problems and the latest results in the papers inspire further research. The volume is recommended to experienced specialists as well as to young researchers and students.

Oh cieca cupidigia, oh ira folie, Che si ci sproni nella vita corta, E nell' eterna poi si mal c'immolle! o blind greediness and foolish rage, That in our fleeting life so goads us on And plunges us in boiling blood for ever! Dante, The Divine Comedy Inferno, XII, 17, 49/51. On an afternoon hike during the second Oberwolfach conference on Mathematical Programming in January 1981, two of the authors of this book discussed a paper by another two of the authors (Korte and Schrader [1981]) on approximation schemes for optimization problems over independence systems and matroids. They had noticed that in many proofs the hereditary property of independence systems and matroids is not needed: it is not required that every subset of a feasible set is again feasible. A much weaker property is sufficient, namely that every feasible set of cardinality k contains (at least) one feasible subset of cardinality k - 1. We called this property accessibility, and that was the starting point of our investigations on greedoids.