**Colloquium Publications**

Volume: 60;
2012;
475 pp;
Hardcover

MSC: Primary 05;
Secondary 90

Print ISBN: 978-0-8218-9085-1

Product Code: COLL/60

List Price: $99.00

Individual Member Price: $79.20

**Electronic ISBN: 978-1-4704-1583-9
Product Code: COLL/60.E**

List Price: $99.00

Individual Member Price: $79.20

#### You may also like

#### Supplemental Materials

# Large Networks and Graph Limits

Share this page
*László Lovász*

Recently, it became apparent that a large
number of the most interesting structures and phenomena of the world
can be described by networks. Developing 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
algebraic theory of graph homomorphisms and of the analytic theory of
graph limits.

#### Readership

Graduate students and research mathematicians interested in graph theory and its application to networks.

#### Reviews & Endorsements

Written 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

# Table of Contents

## Large Networks and Graph Limits

- Cover Cover11
- Title page iii4
- Dedication v6
- Contents vii8
- Preface xi12
- Part 1. Large graphs: An informal introduction 116
- Very large networks 318
- Large graphs in mathematics and physics 2540
- Part 2. The algebra of graph homomorphisms 3550
- Notation and terminology 3752
- Graph parameters and connection matrices 4156
- Graph homomorphisms 5570
- Graph algebras and homomorphism functions 8398
- Part 3. Limits of dense graph sequences 113128
- Kernels and graphons 115130
- The cut distance 127142
- Szemerédi partitions 141156
- Sampling 157172
- Convergence of dense graph sequences 173188
- Convergence from the right 201216
- On the structure of graphons 217232
- The space of graphons 239254
- Algorithms for large graphs and graphons 263278
- Extremal theory of dense graphs 281296
- Multigraphs and decorated graphs 317332
- Part 4. Limits of bounded degree graphs 327342
- Graphings 329344
- Convergence of bounded degree graphs 351366
- Right convergence of bounded degree graphs 367382
- On the structure of graphings 383398
- Algorithms for bounded degree graphs 397412
- Part 5. Extensions: A brief survey 413428
- Other combinatorial structures 415430
- Appendix A 433448
- Bibliography 451466
- Author index 465480
- Subject index 469484
- Notation index 473488
- Back Cover Back Cover1494