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.G...G of some base graph G as the number of factors tends to infinity. We propose a natural asymptotic lower bound on the first-passage time between (v,v,.,v) and (w,w,.,w) as n, the number of factors, tends to infinity, which we call the critical time t.G(v,w). Our main result characterizes when this lower bound is sharp as n... As a corollary, we are able to determine the limit of the so-called diagonal time-constant in Zn as n.. for a large class of distributions of passage times.