The Social Network Model on Infinite Graphs

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).