RANDOM SUBGRAPHS IN SPARSE GRAPHS.

We investigate the threshold probability for connectivity of sparse graphs under weak assumptions. As a corollary this completely solves the problem for Cartesian powers of arbitrary graphs. In detail, let G be a connected graph on k vertices, Gn be the nth Cartesian power of G, αi be the number of vertices of degree i of G, λ be a positive real number, and Gnp be the graph obtained from Gn by deleting every edge independently with probability 1 − p. If ∑i αi(1 − p)i = λ 1/n , then limn→∞ ℙ[Gnp is connected] = exp(−λ). This result extends known results for regular graphs. The main result implies that the threshold probability does not depend on the graph structure of G itself, but only on the degree sequence of the graph. [ABSTRACT FROM AUTHOR]