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.
Users
Please
log in to take part in the discussion (add own reviews or comments).