Asymptotics for first-passage percolation on logarithmic subgraphs of ${\mathbb{Z}}^2$

Abstract

For $a>0$ and $b\ge 0$, let ${\mathbb{G}}_{a,b}$ be the subgraph of ${\mathbb{Z}}^2$ induced by the vertices between the first coordinate axis and the graph of the function $f=f_{a,b}(u)=a\log (1+u)+b\log (1+\log (1+u))$, $u\ge 0$. It is known that for $a>0$, the critical value for Bernoulli percolation on ${\mathbb{G}}_f={\mathbb{G}}_{a,b}$ is strictly between $1/2$ and $1$, and that if $b>2a$ then the percolation phase transition is discontinuous. We study first-passage percolation (FPP) on ${\mathbb{G}}_{a,b}$ with i.i.d. edge-weights $({\tau }_e)$ satisfying $p=\mathbb{P}({\tau }_e=0)\in [1/2,1)$ and the "gap condition" $\mathbb{P}({\tau }_e\le \delta )=p$ for some $\delta >0$. We find the rate of growth of the expected passage time in ${\mathbb{G}}_f$ from the origin to the line $x=n$, and show that, while when $p=1/2$ it is of order $n/(a\log n)$, when $p>1/2$ it can be of order (a) $n^{c_1}/(\log n{)}^{c_2}$, (b) $(\log n{)}^{c_3}$, (c) $\log \log n$, or (d) constant, depending on the relationship between $a,b,$ and $p$. For more general functions $f$, we prove a central limit theorem for the passage time and show that its variance grows at the same rate as the mean. As a consequence of our methods, we improve the percolation transition result by showing that the phase transition on ${\mathbb{G}}_{a,b}$ is discontinuous if and only if $b>a$, and improve "sponge crossing dimensions" asymptotics from the '80s on subcritical percolation crossing probabilities for tall thin rectangles.

58 pages, 2 figures, minor errors corrected on p. 48