Large Networks and Graph Limits - 9780821890851

While working with the Theory Group of Microsoft Research in 2003, three interrelated issues were raised to the author: which functions on finite graphs can be represented as partition functions of models from statistical physics, whether the notion of "limit distribution" was applicable to sequences of graphs, and whether results about quasirandom graphs can be generalized to multitype quasirandom graphs. The answers to these questions were found through work characterizing graphs through homomorphism numbers, the study of normalized versions of homomorphism numbers and their limits, an algebraic theory of graph homorphisms, and an analytic theory of convergence of graph sequences and their limits. In this volume, he lays out the results of that work, both within the field of graph theory and in terms of connections to other classical and non-classical parts of mathematics. The material is presented in five main parts addressing the mathematics of large networks, the algebraic treatment of homomorphism functions and other graph parameters, the theory of convergent sequences of dense graphs and its applications to extremal graph theory and graph algorithms, the theory of convergent sequences of graphs with bounded degree, and possible extensions of the results. Annotation ©2013 Book News, Inc., Portland, OR (booknews.com)