The small world effect on the coalescing time of random walks (Q544499)

A random graph is constructed starting from a deterministic graph either by adding random connections, or by removing some connections randomly, as for percolation. Particular classes of random graphs of the first type are small world graphs, constructed starting from a \(d\)-dimensional (discrete) torus of size \(2L\), whose edges are called short range connections, adding some random connections, called long range connections. The authors study the asymptotic behavior of the meeting time \(T\) of two random walks moving on this small world and compare it with the result on the torus. On the torus, in order to have convergence, the authors rescale \(T\) by a dimension dependent factor. They prove that the walks always meet faster on the small world graphs than on the torus if \(d \leq 2\), while if \(d \geq 3\), this depends on the probability of moving along the random connection. As an application, the authors obtain results on the hitting time to the origin of a single walk and on the convergence of coalescing random walk systems on small world graphs.