Mobile geometric graphs: detection, coverage and percolation (Q1955843)

The authors consider a dynamic Boolean model introduced by van den Berg, Meester and White. This is a model of a random graph evolving in time. The vertices of the graph are given by points in the \(d\)-dimensional Euclidean space distributed initially according to a Poisson point process with a constant intensity and then moving according to independent standard Brownian motions. Edges are drawn between pairs of vertices that are within distance at most a given constant from each other. The authors study large time asymptotics for the following stopping times: (1) detection time, the first time when an auxiliary point moving independently from the vertices of the graph (called ``target'' point) gets within a certain distance from the vertex set of the graph, (2) coverage time, the first time when all the points of a given set have been detected, and (3) percolation time, the first time when a target point gets within a certain distance from a vertex in an infinite connected component of the graph. The authors prove the following results. If the movement of the target point is deterministic and continuous, the authors give an explicit expression for the distribution of the detection time. If the movement of the target point is random, the authors prove upper bounds on the tail of the distribution, and if the target point moves according to a standard Brownian motion, they prove complementary lower bounds, which are tight in dimensions 1 and 2. All the expressions involve the expected volume of a Wiener sausage. The authors obtain an explicit asymptotic expression for the expected coverage time of an enlarged bounded set with a well-defined Minkowski dimension as the enlargement factor increases. They also show that the coverage time is asymptotically concentrated around its mean. In the case when the target point is not moving or moves according to a standard Brownian motion, the authors prove an upper bound on the tail of the distribution of the percolation time. Complementary lower bounds come for free from the estimates on the detection time. The bounds are tight up to a logarithmic correction. This is the most technical part of the paper. The proof is based on a multi-scale argument and a coupling of the evolution of the graph with an independent Poisson point process of a slightly smaller intensity. Possible applications of the results may be in the study of mobile ad hoc networks with decentralized transmission rules.