zbMATH — the first resource for mathematics

The social network model on infinite graphs. (English) Zbl 1459.60145
Summary: Given an infinite connected regular graph \(G=(V,E)\), place at each vertex \(\operatorname{Poisson}(\lambda)\) 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 \(\lambda>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 \(\lambda_{\text{c}}(G)>0\). We give general bounds on \(\lambda_{\text{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 \(\lambda\) there exists a finite time \(t_{\lambda}(G)\) such that a.s. there exists an infinite set of walkers having a path of acquaintances between them by time \(t_{\lambda}(G)\).
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
60G50 Sums of independent random variables; random walks
60K35 Interacting random processes; statistical mechanics type models; percolation theory
82C41 Dynamics of random walks, random surfaces, lattice animals, etc. in time-dependent statistical mechanics
82B43 Percolation
Full Text: DOI Euclid
[1] Alves, O. S. M., Machado, F. P. and Popov, S. Yu. (2002). The shape theorem for the frog model. Ann. Appl. Probab. 12 533-546. · Zbl 1013.60081
[2] Benjamini, I. (2012). Private communication.
[3] Benjamini, I., Fontes, L. R., Hermon, J. and Machado, F. P. (2016). On an epidemic model on finite graphs. Ann. Appl. Probab. To appear. Available at arXiv:1610.04301. · Zbl 1434.82074
[4] Benjamini, I. and Hermon, J. (2019). Rapid social connectivity. Electron. J. Probab. 24 Art. ID 32. · Zbl 1419.82053
[5] Benjamini, I., Nachmias, A. and Peres, Y. (2011). Is the critical percolation probability local? Probab. Theory Related Fields 149 261-269. · Zbl 1230.60099
[6] Gandolfi, A., Keane, M. S. and Newman, C. M. (1992). Uniqueness of the infinite component in a random graph with applications to percolation and spin glasses. Probab. Theory Related Fields 92 511-527. · Zbl 0767.60098
[7] Gantert, N. and Müller, S. (2006). The critical branching Markov chain is transient. Markov Process. Related Fields 12 805-814. · Zbl 1115.60077
[8] Hermon, J. and Hutchcroft, H. (2019). Supercritical percolation on nonamenable graphs: Isoperimetry, analyticity, and exponential decay of the cluster size distribution. Preprint. Available at arXiv:1904.10448.
[9] Hoffman, C., Johnson, T. and Junge, M. (2016). From transience to recurrence with Poisson tree frogs. Ann. Appl. Probab. 26 1620-1635. · Zbl 1345.60116
[10] Hoffman, C., Johnson, T. and Junge, M. (2017). Recurrence and transience for the frog model on trees. Ann. Probab. 45 2826-2854. · Zbl 1385.60058
[11] Kesten, H. and Sidoravicius, V. (2005). The spread of a rumor or infection in a moving population. Ann. Probab. 33 2402-2462. · Zbl 1111.60074
[12] Lyons, R. and Oveis Gharan, S. (2018). Sharp bounds on random walk eigenvalues via spectral embedding. Int. Math. Res. Not. IMRN 2018 7555-7605. · Zbl 1419.05132
[13] Lyons, R. and Peres, Y. (2016). Probability on Trees and Networks. Cambridge Series in Statistical and Probabilistic Mathematics 42. Cambridge Univ. Press, New York.
[14] Popov, S. Yu. (2001). Frogs in random environment. J. Stat. Phys. 102 191-201. · Zbl 0972.60101
[15] Teixeira, A. and Tykesson, J. (2013). Random interlacements and amenability. Ann. Appl. Probab. 23 923-956. · Zbl 1375.60139
[16] Telcs, A. · Zbl 0967.60059
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.