First-passage percolation on Cartesian power graphs

We consider first-passage percolation on the class of “high-dimensional” graphs that can be written as an iterated Cartesian product $G\square G \square \dots \square G$ofsomebasegraph$G$ as the number of factors tends to infinity. We propose a natural asymptotic lower bound on the first-passage time between $(v,v,\dots ,v)$ and $(w,w,\dots ,w)$ as $n$, the number of factors, tends to infinity, which we call the critical time $t_G^{\ast }(v,w)$. Our main result characterizes when this lower bound is sharp as $n\to \mathrm{\infty }$. As a corollary, we are able to determine the limit of the so-called diagonal time-constant in ${\mathbb{Z}}^n$ as $n\to \mathrm{\infty }$ for a large class of distributions of passage times.