A simple solution to the k-core problem

Details A simple solution to the k-core problem A simple solution to the k-core problem

2005-08-24

arxiv.org/abs/math/0508453v1

Mathematics

Combinatorics

14 pages

Scientific paper

We study the k-core 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 the k-core is empty, and other conditions that imply that with high probability the k-core is non-empty 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 result by Pittel, Spencer and Wormald on the existence and size of a k-core in G(n,p) and G(n,m). 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 simple solution to the k-core 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 simple solution to the k-core problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A simple solution to the k-core problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-269417