On the connectivity threshold of Achlioptas processes (Q482273)

This paper studies the connectivity threshold of Achlioptas processes. The random graph in question becomes connected with high probability as the number of vertices \(n\) tends to infinity when the number of edges is asymptotically \(\frac14n\ln n\). This is shown via examining the emergence of giant components and the differential equations method for the phase transition in bounded-size Achlioptas processes. Moreover, the connectivity threshold of the Bohman-Frieze processes is also discussed with similar line of reasoning.