A new approach to the giant component problem

Details A new approach to the giant component problem A new approach to the giant component problem

2007-07-12

arxiv.org/abs/0707.1786v1

Mathematics

Combinatorics

21 pages

Scientific paper

We study the largest component of a random (multi)graph on n vertices with a given degree sequence. We let n tend to infinity. Then, under some regularity conditions on the degree sequences, we give conditions on the asymptotic shape of the degree sequence that imply that with high probability all the components are small, and other conditions that imply that with high probability there is a giant component and the sizes of its vertex and edge sets satisfy a law of large numbers; under suitable assumptions these are the only two possibilities. In particular, we recover the results by Molloy and Reed on the size of the largest component in a random graph with a given degree sequence. We further obtain a new sharp result for the giant component just above the threshold, generalizing the case of G(n,p) with np=1+omega(n)n^{-1/3}, where omega(n) tends to infinity arbitrarily slowly. Our method is based on the properties of empirical distributions of independent random variables, and leads to simple proofs.

Affiliated with

Also associated with

No associations

Rating

A new approach to the giant component problem 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 A new approach to the giant component problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A new approach to the giant component problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-161174