Critical first passage percolation on random graphs

Abstract

In 1999, Zhang proved that for first passage percolation on the square lattice Z2 with i.i.d. nonnegative passage times on each edge, if the probability that an edge has zero passage time is exactly 1/2 (the critical threshold for bond percolation on Z2), then the passage time from the origin to the boundary of [−n,n]2 may either diverge to infinity or remain bounded, depending on the nature of the passage-time distribution near zero. In 2017, Damron, Lam, and Wang gave an easily checkable necessary and sufficient condition for the passage time to remain bounded on the two dimensional lattice Z2. Here, we consider the analogous problem studied by Zhang, but now for a sequence of random graphs generated according to the configuration model. The main question of interest is: when does the passage time between two randomly chosen vertices converge in distribution as the network size n→∞? There are interesting similarities between the answers on Z2 and on random graphs, but it is easier for the passage times on random graphs to stay bounded.