Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing

Details Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing

2007-01-31

arxiv.org/abs/math/0702004v1

Mathematics

Combinatorics

57 pages. See also http://research.microsoft.com/~borgs/. This version differs from an earlier version from May 2006 in the or

Scientific paper

We consider sequences of graphs and define various notions of convergence related to these sequences: ``left convergence'' defined in terms of the densities of homomorphisms from small graphs into the graphs of the sequence, and ``right convergence'' defined in terms of the densities of homomorphisms from the graphs of the sequence 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, and for graphs 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 Szemeredi partitions, sampling and testing of large graphs.

Affiliated with

Also associated with

No associations

Rating

Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-348143