zbMATH — the first resource for mathematics

Large networks and graph limits. (English) Zbl 1292.05001
Colloquium Publications. American Mathematical Society 60. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-9085-1/hbk). xiv, 475 p. (2012).
Motivated by the increasing emergence of large networks and the challenges they pose, this book presents a mathematical theory of large graphs and their limits, both for the case of dense and sparse graphs. It is divided into five main parts: 1) Mathematical challenges provided by large networks; 2) An algebraic treatment of homomorphism functions and other graph parameters (graph parameters and connection matrices, graph homomorphisms, graph algebras and homomorphism functions); 3) A theory of convergent sequences of dense graphs (kernels and graphons, the cut distance, Szemerédi partitions, sampling, convergence of dense graph sequences, convergence from the right, the structure and the space of graphons, algorithms for large graphs and graphons, extremal theory of dense graphs, multigraphs and decorated graphs); 4) Limits of bounded degree graphs (graphings, convergence of bounded degree graphs, convergence from the right, the structure of graphings, algorithms for bounded degree graphs); and 5) Extensions to edge-coloring models, hypergraphs and categories. The various connections with other branches of mathematics are highlighted: statistical physics (study of local/global properties of very large graphs), computer science (theory of property testing), analysis (measure theory, functional analysis) and algebra (representation theory of algebras, combinatorial theory of categories, group theory with sofic groups). Many examples and a number of graduate-level exercises are included.
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.

05-02 Research exposition (monographs, survey articles) pertaining to combinatorics
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C42 Density (toughness, etc.)
05C80 Random graphs (graph-theoretic aspects)
05C35 Extremal problems in graph theory
05C82 Small world graphs, complex networks (graph-theoretic aspects)
05C63 Infinite graphs
68R10 Graph theory (including graph drawing) in computer science
05C90 Applications of graph theory