## Abstract

Given an infinite connected regular graph G = (V ,E), place at each vertex Poisson(λ) walkers performing independent lazy simple random walks on G simultaneously. When two walkers visit the same vertex at the same time they are declared to be acquainted. We show that when G is vertex-transitive and amenable, for all λ > 0 a.s. any pair of walkers will eventually have a path of acquaintances between them. In contrast, we show that when G is nonamenable (not necessarily transitive) there is always a phase transition at some λc(G) > 0.We give general bounds on λc(G) and study the case that G is the d-regular tree in more detail. Finally, we show that in the nonamenable setup, for every λ there exists a finite time tλ(G) such that a.s. there exists an infinite set of walkers having a path of acquaintances between them by time tλ(G).

Original language | English (US) |
---|---|

Pages (from-to) | 902-935 |

Number of pages | 34 |

Journal | Annals of Applied Probability |

Volume | 30 |

Issue number | 2 |

DOIs | |

State | Published - Apr 2020 |

## All Science Journal Classification (ASJC) codes

- Statistics and Probability
- Statistics, Probability and Uncertainty

## Keywords

- Amenability
- Infinite cluster
- Percolation
- Phase transition
- Random walks
- Social network