First-passage percolation on Cartesian power graphs

Abstract: We consider first-passage percolation on the class of "high-dimensional" graphs that can be written as an iterated Cartesian product

G s q u a r e G s q u a r e d o t s s q u a r e 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, d o t s, v)

and

(w, w, d o t s, 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 i g h t a r r o w i n f t y

. As a corollary, we are able to determine the limit of the so-called diagonal time-constant in

m a t h b b Z^{n}

as

n i g h t a r r o w i n f t y

for a large class of distributions of passage times.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: First-passage percolation on Cartesian power graphs