Connectivity in one-dimensional geometric random graphs: Poisson approximations, zero-one laws and phase transitions

Abstract

Consider n points (or nodes) distributed uniformly and independently on the unit interval [0,1]. Two nodes are said to be adjacent if their distance is less than some given threshold value.For the underlying random graph we derive zero-one laws for the property of graph connectivity and give the asymptotics of the transition widths for the associated phase transition. These results all flow from a single convergence statement for the probability of graph connectivity under a particular class of scalings. Given the importance of this result, we give two separate proofs; one approach relies on results concerning maximal spacings, while the other one exploits a Poisson convergence result for the number of breakpoint users.