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.

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.

Reviewer: Reinhardt Euler (Brest)

##### MSC:

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 |