Let $V_\rho\subset\mathbb{R}^2$ be a point set in the plane obtained from a Poisson process of density $\rho$. The random geometric graph $G_\rho$ is obtained from $V_\rho$ by connecting points that have Euclidean distance smaller than one. Let us assume that $\rho$ is larger than the critical density (in fact, we will later consider $\rho\to\infty$), such that there is a unique infinite component $G_{\rho}^0$. Let us assume w.l.o.g. that $0\in G_\rho^0$.

To each edge $e$ of $G_\rho^0$ we assign a positive i.i.d. random delay $\tau_e$ with pdf $P(\tau_e)$. The first passage time $T(x)$ for $x\in G_\rho^0$ is given by minimal total delay among all paths $\gamma$ from 0 to $x$, i.e.

$$T(x)=\min_{\gamma:0\to x}\sum_{e\in\gamma}\tau_e.$$ Let the hop count $H(x)$ be the number of edges in the path of shortest delay (assuming it exists and is unique).

Using subadditive ergodic theory (Kingman, 1973) it has been shown that under mild conditions on $P(\tau_e)$ the passage time $T(x)$ almost surely scales linearly with $|x|$ in the large $|x|$ limit. However, to my knowledge no exact values for the scaling constant, which is often called the time constant, are known. The same seems to be true for the hop count constant $h_\rho$, i.e.

$$h_\rho = \lim_{|x|\to\infty}\frac{H(x)}{|x|}.$$

So how about the limiting situation $\rho\to\infty$, in which the connectivity becomes very large? Assuming that $P(\tau_e)$ is smooth and non-zero as $\tau_e\to 0$, the first passage time $T(x)$ will go to zero (when keeping $|x|$ fixed). However, the hop count $H(x)$ is by construction bounded from below by $\lceil|x|\rceil$.

Q1: Are any properties known about the time minimizing paths $\gamma$ in the $\rho\to\infty$ limit?

Numerical experiments suggest that $h_\infty:=\lim_{\rho\to\infty}h_\rho\approx 2$ independently of the distribution $P(\tau_e)$. Below are some examples of the time-minimizing paths (in blue) for $\rho=10,20,30,40$ and $P(\tau_e)$ the exponential distribution with mean 1. In each case the blue path is roughly twice as long as the shortest path (in red).

Image: http://www.nbi.dk/~budd/images/fpp.png

Q2: Is $h_{\infty} =2$? Is there a simple (heuristic) explanation?

Note: So far the most relevant (recent) literature I have found is in applications to "Wireless sensor networks". Any pointers to more pure mathematics papers in which such hop counts are studied in plane graphs are most welcome.

  • $\begingroup$ Do you expect the underlying point process model to be relevant? Or would you think that something similar could happen e.g. for FPP on the square lattice? $\endgroup$ Sep 8 '14 at 12:04
  • $\begingroup$ Indeed, I would expect it to be independent of the set $V_\rho$ in the $\rho\to\infty$ limit as long as the large scale density is approximately uniform. In that case taking $V_\rho = \rho^{-2}\mathbb{Z}^2$ should lead to the same result, but I can't prove this. More generally, one might ask whether in any sense these models converge as $\rho\to\infty$ to a (universal) model of discrete paths on $\mathbb{R}^2$. To achieve that it is presumably necessary to consider passage times not between individual points, but between disks of radius $R(\rho)$ with suitable dependence on $\rho$. $\endgroup$ Sep 8 '14 at 14:45
  • $\begingroup$ It should not be difficult to show that $h_\infty$ does not depend on the distribution as soon as $P$ has positive density and no atom at $0$: indeed, as soon as bonds with small weight percolate "enough", they should be the only ones present on the shortest path, at least asymptotically as $\rho\to\infty$. $\endgroup$ Sep 8 '14 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.