Metrics for sparse graphs

Details Metrics for sparse graphs Metrics for sparse graphs

2007-08-14

arxiv.org/abs/0708.1919v3

in Surveys in Combinatorics 2009, LMS Lecture Notes Series 365, CUP 2009, pp. 211--287

Mathematics

Combinatorics

83 pages, 1 figure. References updated and one corrected

Scientific paper

Recently, Bollob\'as, Janson and Riordan introduced a very general family of random graph models, producing inhomogeneous random graphs with $\Theta(n)$ edges. Roughly speaking, there is one model for each {\em kernel}, i.e., each symmetric measurable function from $[0,1]^2$ to the non-negative reals, although the details are much more complicated. A different connection between kernels and random graphs arises in the recent work of Borgs, Chayes, Lov\'asz, S\'os, Szegedy and Vesztergombi. They introduced several natural metrics on dense graphs (graphs with $n$ vertices and $\Theta(n^2)$ edges), showed that these metrics are equivalent, and gave a description of the completion of the space of all graphs with respect to any of these metrics in terms of {\em graphons}, which are essentially bounded kernels. One of the most appealing aspects of this work is the message that sequences of inhomogeneous quasi-random graphs are in a sense completely general: any sequence of dense graphs contains such a subsequence. Our aim here is to briefly survey these results, and then to investigate to what extent they can be generalized to graphs with $o(n^2)$ edges. Although many of the definitions extend in a simple way, the connections between the various metrics, and between the metrics and random graph models, turn out to be much more complicated than in the dense case. We shall prove many partial results, and state even more conjectures and open problems, whose resolution would greatly enhance the currently rather unsatisfactory theory of metrics on sparse graphs. This paper deals mainly with graphs with $o(n^2)$ but $\omega(n)$ edges: a companion paper [arXiv:0812.2656] will discuss the (more problematic still) case of {\em extremely sparse} graphs, with O(n) edges.

Affiliated with

Also associated with

No associations

Rating

Metrics for sparse graphs 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 Metrics for sparse graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Metrics for sparse graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-389721