%0 Journal Article %1 borgs_convergent_2008 %A Borgs, C. %A Chayes, J.T. %A Lovász, L. %A Sós, V.T. %A Vesztergombi, K. %D 2008 %J Advances in Mathematics %K Free Graph Parameter Partition Sampling, Szemerédi \_tablet, energies, functions, partitions sequences, testing, %N 6 %P 1801--1851 %R 10.1016/j.aim.2008.07.008 %T Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing %U http://www.sciencedirect.com/science/article/pii/S0001870808002053 %V 219 %X We consider sequences of graphs ( G n ) and define various notions of convergence related to these sequences: “left convergence” defined in terms of the densities of homomorphisms from small graphs into G n ; “right convergence” defined in terms of the densities of homomorphisms from G n into small graphs; and convergence in a suitably defined metric. In Part I of this series, we show that left convergence is equivalent to convergence in metric, both for simple graphs G n , and for graphs G n with nodeweights and edgeweights. One of the main steps here is the introduction of a cut-distance comparing graphs, not necessarily of the same size. We also show how these notions of convergence provide natural formulations of Szemerédi partitions, sampling and testing of large graphs.

@article{borgs_convergent_2008, abstract = {We consider sequences of graphs ( G n ) and define various notions of convergence related to these sequences: “left convergence” defined in terms of the densities of homomorphisms from small graphs into G n ; “right convergence” defined in terms of the densities of homomorphisms from G n into small graphs; and convergence in a suitably defined metric. In Part I of this series, we show that left convergence is equivalent to convergence in metric, both for simple graphs G n , and for graphs G n with nodeweights and edgeweights. One of the main steps here is the introduction of a cut-distance comparing graphs, not necessarily of the same size. We also show how these notions of convergence provide natural formulations of Szemerédi partitions, sampling and testing of large graphs.}, added-at = {2017-01-09T13:57:26.000+0100}, author = {Borgs, C. and Chayes, J.T. and Lovász, L. and Sós, V.T. and Vesztergombi, K.}, biburl = {https://www.bibsonomy.org/bibtex/20025f111fbda50efb735b79c6bd54f5a/yourwelcome}, doi = {10.1016/j.aim.2008.07.008}, interhash = {e8729251b9ced9d99c69a33a2f8c344d}, intrahash = {0025f111fbda50efb735b79c6bd54f5a}, issn = {0001-8708}, journal = {Advances in Mathematics}, keywords = {Free Graph Parameter Partition Sampling, Szemerédi \_tablet, energies, functions, partitions sequences, testing,}, month = dec, number = 6, pages = {1801--1851}, shorttitle = {Convergent sequences of dense graphs {I}}, timestamp = {2017-01-09T14:01:11.000+0100}, title = {Convergent sequences of dense graphs {I}: {Subgraph} frequencies, metric properties and testing}, url = {http://www.sciencedirect.com/science/article/pii/S0001870808002053}, urldate = {2013-09-01}, volume = 219, year = 2008 }