Motivated by the increasing importance of growing networks, we consider how to suitably define convergence for a sequence of graphs, with the number of vertices tending to infinity. To this end, we consider two ways of probing a large graph with small graphs: “from the left”, by counting the the number of times a small graph is contained in the large graph as a subgraph, and “from the right”, by counting the number of H-colorings of the large graph, i.e., the number of homomorphisms from the large graph into some small graph H. This leads to two notions of convergence: from the left, corresponding to the convergence of local properties like the frequency of triangles, and from the right, corresponding to more global properties like the number of colorings or the size of the max-cut. We show that these two apparently unrelated notions are equivalent for sequences of dense graphs. We also show how these two types of convergence are related to other interesting notions – cut metrics, sampling and testing of large graphs, Szemeredi partitions, and statistical physics.
This is joint work with Christian Borgs, Laci Lovasz, Vera Sos and Kati Vesztergombi.
Audio (MP3 File, Podcast Ready)
Copyright. All Rights Reserved.