Mathew D. Penrose

Connectivity and singletons in soft geometric graphs

Abstract:

Consider a random graph on n vertices scattered uniformly at random in the unit d-cube (d >1 fixed), in which any two vertices distant at most r apart are connected with probability p. This generalizes some well-known random graph models. We describe how for n large under any choice of the parameter sequence ((r(n),p(n)), n ≥ 1), the probability that the resulting graph is connected is governed by the probability that it is free of isolated vertices, and the number of isolated vertices is approximately Poisson. We describe some aspects of the proof.