On the connectivity threshold of Achlioptas processes

In this paper we study the connectivity threshold of Achlioptas processes. It is well known that the classical Erdös-Rényi random graph with $n$ vertices becomes connected whp (with high probability, i.e., with probability tending to one as $n \to \infty$) when the number of edges is asymptotically $\frac{1}{2} n \log n$. Our first result asserts that the connectivity threshold of the well-studied Bohman-Frieze process, which is known to delay the phase transition, coincides asymptotically with that of the Erdös-Rényi random graph. Moreover, we describe an Achlioptas process that pushes backward the threshold for being connected $\frac{1}{4} n \log n$ edges, i.e., asymptotically half of what is required in the Erdös-Rényi process, are sufficient), but which simultaneously retains the property of delaying the phase transition.

Keywords

Achlioptas process, connectivity

2010 Mathematics Subject Classification

Primary 05C80. Secondary 60C05.

Full Text (PDF format)

Published 29 October 2014