The social network model on infinite graphs

Given an infinite connected regular graph G=(V,E), place at each vertex Poisson(.). 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 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).