Graphs and Geometry
About this Title
László Lovász, Eötvös Loránd University, Budapest, Hungary
Publication: Colloquium Publications
Publication Year: 2019; Volume 65
ISBNs: 978-1-4704-5087-8 (print); 978-1-4704-5354-1 (online)
MathSciNet review: MR3967118
MSC: Primary 05-01; Secondary 05C10, 05C50, 05C62
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.
Geometric representations of graphs lead to significant insights in the study of graph properties and their algorithmic aspects. This book is a thorough study of the subject written by the pioneer of many of the results in the area. It is a fascinating manuscript written by a superb mathematician who is also a fantastic expositor.
—Noga Alon, Princeton University and Tel Aviv University
A beautiful book, rich in intuition, insights, and examples, from one of the masters of combinatorics, geometry, and graph theory. This book presents old friends of graph theory in a new light and introduces more recent developments, providing connections to many areas in combinatorics, analysis, algorithms, and physics. Those of us who know graph theory still have much to learn from this presentation; for those who are new to the field, the book is a wonderful gift and invitation to participate.
—Jennifer Chayes, Microsoft Research
László Lovász is one of the most prominent experts in discrete mathematics. The book is unique and inspiring for students and researchers as well. The author succeeded to show the wealth and beauty of the subject.
—Endre Szemerédi, Rutgers University
Graduate students and researchers interested in graph theory.
Table of Contents
- Why are geometric representations interesting?
- Planar graphs
- Rubber bands
- Discrete harmonic functions
- Coin representation
- Square tilings
- Discrete analytic functions
- Discrete analytic functions: Statistical physics
- Adjacency matrix and its square
- Orthogonal representations: Dimension
- Orthogonal representations: The smallest cone
- Orthogonal representations: Quantum physics
- Semidefinite optimization
- Rigidity and motions of frameworks
- The Colin de Verdière number
- Metric representations
- Matching and covering in frameworks
- Combinatorics of subspaces
- Concluding thoughts
- Appendix A. Linear algebra
- Appendix B. Graphs
- Appendix C. Convex bodies