The evolution of the min-min random graph process
By Amin Coja-Oghlan and Mihyun KangSubmitted
Abstract
We study the min-min random graph process {G0,G1,...}: the initial state G0 is an empty graph on n vertices (n even). Moreover, GM+1 is obtained from GM by choosing a pair {v,w} of vertices of GM of minimum degree uniformly at random among all such pairs and adding the edge {v,w}. We show that GM is asymptotically almost surely disconnected if M < = n, and that for M=(1+t)n, 0 < t < =1/2 constant, the probability that GM is connected increases from 0 to 1. Furthermore, we investigate the number X of vertices outside of the largest component of GM. For 0 < t < 1/2 constant we derive the precise limiting distribution of X. In addition, for n-1 log4 n < = t=o(1) we show that tX converges to a gamma distribution.
Download
- ps.gz- minmin.pdf
