Description
Book SynopsisTrade ReviewWritten by an eminent expert as the first monograph on this topic, this book can be recommended to anybody working on large networks and their applications in mathematics, computer science, social sciences, biology, statistical physics or chip design." -
Zentralblatt Math"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
"It is always exciting when a mathematical theory turns out to be connected to a variety of other topics. This is the case with the recently developed subject of graph limits, which exhibits tight relations with a wide range of areas including statistical physics, analysis, algebra, extremal graph theory, and theoretical computer science. The book
Large Networks and Graph Limits contains a comprehensive study of this active topic and an updated account of its present status. The author, Laszls Lovasz, initiated the subject, and together with his collaborators has contributed immensely to its development during the last decade. This is a beautiful volume written by an outstanding mathematician who is also an excellent 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 by taking one of the most quintessentially combinatorial of objects--the finite graph--and through the process of taking limits of sequences of such graphs, reveals and clarifies connections to measure theory, analysis, statistical physics, metric geometry, spectral theory, property testing, algebraic geometry, and even Hilbert's tenth and seventeenth problems. Indeed, 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
"László Lovász 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 Lovász'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
Table of Contents
- Preface
- Part 1. Large graphs: An informal introduction
- Very large networks
- Large graphs in mathematics and physics
- Part 2. The algebra of graph homomorphisms
- Notation and terminology
- Graph parameters and connection matrices
- Graph homomorphisms
- Graph algebras and homomorphism functions
- Part 3. Limits of dense graph sequences
- Kernels and graphons
- The cut distance
- Szemerédi partitions
- Sampling
- Convergence of dense graph sequences
- Convergence from the right
- On the structure of graphons
- The space of graphons
- Algorithms for large graphs and graphons
- Extremal theory of dense graphs
- Multigraphs and decorated graphs
- Part 4. Limits of bounded degree graphs
- Graphings
- Convergence of bounded degree graphs
- Right convergence of bounded degree graphs
- On the structure of graphings
- Algorithms for bounded degree graphs
- Part 5. Extensions: A brief survey
- Other combinatorial structures
- Appendix A
- Bibliography
- Author index
- Subject index
- Notation index
