## Large Networks and Graph LimitsRecently, 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 |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

3 | |

Large graphs in mathematics and physics | 25 |

Notation and terminology | 37 |

Graph homomorphisms | 55 |

Graph algebras and homomorphism functions | 83 |

Kernels and graphons | 115 |

The cut distance | 127 |

Szemerédi partitions | 141 |

Extremal theory of dense graphs | 281 |

Multigraphs and decorated graphs | 317 |

Graphings | 329 |

Convergence of bounded degree graphs | 351 |

Right convergence of bounded degree graphs | 367 |

On the structure of graphings | 383 |

Algorithms for bounded degree graphs | 397 |

Other combinatorial structures | 415 |

Sampling | 157 |

Convergence of dense graph sequences | 173 |

Convergence from the right | 201 |

On the structure of graphons | 217 |

The space of graphons | 239 |

Algorithms for large graphs and graphons | 263 |

Appendix A Appendix | 433 |

451 | |

465 | |

473 | |

### Common terms and phrases

algebra algorithm automorphism bipartite graph Borel sets bounded degree graphs colors complete graph compute connected component consider construction convergent graph sequence Corollary countable cut distance cut norm define deﬁnition dense graphs edgeweights equivalent Example Exercise extremal graph ﬁnite finite connection rank finite graphs finitely forcible follows graph G graph parameter graph property graphon hence hom(F homomorphism densities homomorphism numbers hyperfinite idempotent implies induced subgraph inequality involution invariant isomorphism k-labeled kernel labeled graphs labeled nodes large graph Let f Let G limit object linear matrix measure preserving map morphisms multigraph multiplicative nodes nodeweights nonnegative number of edges number of nodes parameter f partition polynomial probability distribution probability space Proposition prove quantum graph quasirandom random graph random graph model Regularity Lemma sampling Section sigma-algebra signed graph simple graph stepfunction subgraph densities subset tensor testable topology trivial ultraproduct weakly isomorphic weighted graph