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

Mihyun Kang (Institute of Optimization and Discrete Mathematics, Graz University of Technology, Graz, Austria)

Konstantinos Panagiotou (Mathematical Institute, University of Munich, Germany)

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.

Full Text (PDF format)