Contents Online

# Journal of Combinatorics

## Volume 5 (2014)

### Number 3

### On the connectivity threshold of Achlioptas processes

Pages: 291 – 304

DOI: http://dx.doi.org/10.4310/JOC.2014.v5.n3.a2

#### Authors

#### Abstract

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.