FIRST-PASSAGE PERCOLATION ON CARTESIAN POWER GRAPHS

• 成果类型: Article
• 署名作者: Martinsson, Anders
• 署名单位: Chalmers University of Technology; University of Gothenburg
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/17-AOP1199
• 发表日期: 2018
• 页码: 1004-1041
• 关键词: 1st passage percolation; dimensions

摘要

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...square 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 ->infinity. As a corollary, we are able to determine the limit of the so-called diagonal time-constant in Z(n) as n ->infinity for a large class of distributions of passage times.