Phase transitions for Erdos-Renyi graphs

arXiv1409.2606MaRDI QIDQ6254512FDOQ6254512

Publication date: 9 September 2014

Abstract: Consider the complete graph on (n) vertices where each edge is independently open with probability (p,) or closed otherwise. Phase transitions for such graphs for (p = frac{C}{n}) have previously been studied using techniques like branching processes and random walks. In this paper, we use an alternate component counting argument for establishing phase transition and obtaining estimates on the sum size of the non-giant components. As a corollary, we also obtain estimates on the size of the giant component for (C) large: If (C) is sufficiently large, there is a positive constant (M_0 = M_0(C)) so that with probability at least (1-e^{-C/100},) there is a giant component containing at least (n - ne^{-C/8}) vertices and every other component contains less than (M_0 log{n}) vertices.

This page was built for publication: Phase transitions for Erdos-Renyi graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6254512)