Limits of randomly grown graph sequences

Details Limits of randomly grown graph sequences Limits of randomly grown graph sequences

2009-05-23

arxiv.org/abs/0905.3806v1

Mathematics

Combinatorics

17 pages, 8 figures

Scientific paper

Motivated in part by various sequences of graphs growing under random rules (like internet models), convergent sequences of dense graphs and their limits were introduced by Borgs, Chayes, Lov\'asz, S\'os and Vesztergombi and by Lov\'asz and Szegedy. In this paper we use this framework to study one of the motivating class of examples, namely randomly growing graphs. We prove the (almost sure) convergence of several such randomly growing graph sequences, and determine their limit. The analysis is not always straightforward: in some cases the cut distance from a limit object can be directly estimated, in other case densities of subgraphs can be shown to converge.

Affiliated with

Also associated with

No associations

Rating

Limits of randomly grown graph sequences 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 Limits of randomly grown graph sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Limits of randomly grown graph sequences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-499504