Explosive Percolation in Erdös-Rényi-Like Random Graph Processes

Computer Science – Discrete Mathematics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

The evolution of the largest component has been studied intensely in a variety of random graph processes, starting in 1960 with the Erd\"os-R\'enyi process. It is well known that this process undergoes a phase transition at n/2 edges when, asymptotically almost surely, a linear-sized component appears. Moreover, this phase transition is continuous, i.e., in the limit the function f(c) denoting the fraction of vertices in the largest component in the process after cn edge insertions is continuous. A variation of the Erd\"os-R\'enyi process are the so-called Achlioptas processes in which in every step a random pair of edges is drawn, and a fixed edge-selection rule selects one of them to be included in the graph while the other is put back. Recently, Achlioptas, D'Souza and Spencer (2009) gave strong numerical evidence that a variety of edge-selection rules exhibit a discontinuous phase transition. However, Riordan and Warnke (2011) very recently showed that all Achlioptas processes have a continuous phase transition. In this work we prove discontinuous phase transitions for a class of Erd\"os-R\'enyi-like processes in which in every step we connect two vertices, one chosen randomly from all vertices, and one chosen randomly from a restricted set of vertices.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Explosive Percolation in Erdös-Rényi-Like Random Graph Processes 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 Explosive Percolation in Erdös-Rényi-Like Random Graph Processes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Explosive Percolation in Erdös-Rényi-Like Random Graph Processes will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-717924

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.