Mathematics – Probability
Scientific paper
2011-11-26
Mathematics
Probability
14 pages
Scientific paper
In Achlioptas processes, starting from an empty graph, in each step two potential edges are chosen uniformly at random, and using some rule one of them is selected and added to the evolving graph. The evolution of the rescaled size of the largest component in such variations of the Erd\H{o}s--R\'enyi random graph process has recently received considerable attention, in particular for the so-called product rule. In this work we establish the following result for rules such as the product rule: the limit of the rescaled size of the `giant' component exists and is continuous provided that a certain system of differential equations has a unique solution. In fact, our result applies to a very large class of Achlioptas-like processes. Our proof relies on a general idea which relates the evolution of stochastic processes to an associated system of differential equations. Provided that the latter has a unique solution, our approach shows that certain discrete quantities converge (after appropriate rescaling) to this solution.
Riordan Oliver
Warnke Lutz
No associations
LandOfFree
Convergence of Achlioptas processes via differential equations with unique solutions 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 Convergence of Achlioptas processes via differential equations with unique solutions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Convergence of Achlioptas processes via differential equations with unique solutions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-484003