zbMATH — the first resource for mathematics

How universal are asymptotics of disconnection times in discrete cylinders? (English) Zbl 1134.60061
For large connected graphs \((G, \mathcal E)\) of uniformly bounded degree, the disconnection time of \(G\times \mathbb Z\) has rough order \(| G| ^2\) for large \(| G| \).

60K35 Interacting random processes; statistical mechanics type models; percolation theory
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
82B41 Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics
60C05 Combinatorial probability
Full Text: DOI Euclid arXiv
[1] Aldous, D. (1983). On the time taken by random walks on finite groups to visit every state. Z. Wahrsch Verw. Gebiete 62 361–374. · Zbl 0488.60011
[2] Aldous, D. and Fill, J. (2007). Reversible Markov Chains and Random Walks on Graphs . To appear. Available at http://www.stat.berkeley.edu/ãldous/RWG/book.html. · Zbl 0684.60055
[3] Barlow, M. T. (2004). Which values of the volume growth and escape time exponent are possible for a graph? Rev. Mat. Iberoam. 20 1–31. · Zbl 1051.60071
[4] Barlow, M. T., Coulhon, T. and Kumagai, T. (2005). Characterization of sub-Gaussian heat kernel estimates on strongly recurrent graphs. Comm. Pure Appl. Math. 58 1642–1677. · Zbl 1083.60060
[5] Brummelhuis, M. J. A. M. and Hilhorst, M. J. (1991). Covering a finite lattice by a random walk. Physica A. 176 387–408.
[6] Delmotte, T. (1999). Parabolic Harnack inequality and estimates of Markov chains on graphs. Rev. Mat. Iberoam. 15 181–232. · Zbl 0922.60060
[7] Dembo, A., Peres, Y., Rosen, J. and Zeitouni, O. (2004). Cover times for Brownian motion and random walks in two dimensions. Ann. Math. 160 433–464. · Zbl 1068.60018
[8] Dembo, A. and Sznitman, A. S. (2006). On the disconnection of a discrete cylinder by a random walk. Probab. Theory Related Fields . 36 321–340. · Zbl 1105.60029
[9] Ethier, S. M. and Kurtz, T. G. (1986). Markov Processes . Wiley, New York. · Zbl 0592.60049
[10] Grigoryan, A. and Telcs, A. (2001. Sub-Gaussian estimates of heat kernels on infinite graphs. Duke Math. J. 109 451–510. · Zbl 1010.35016
[11] Grigoryan, A. and Telcs, A. (2002). Harnack inequalities and sub-Gaussian estimates for random walks. Math. Ann. 324 521–556. · Zbl 1011.60021
[12] Khaśminskii, R. Z. (1959). On positive solutions of the equation \(Au + Vu = 0\). Theory Probab. Appl. 4 309–318. · Zbl 0089.34501
[13] Lubotzky, A. (1994). Discrete Groups , Expanding Graphs and Invariant Measures . Birkhäuser, Basel. · Zbl 0826.22012
[14] Saloff-Coste, L. (1997). Lectures on finite Markov chains. In Ecole d ’ Eté de Probabilités de Saint Flour (P. Bernard, ed.). Lectures Notes in Math. 1665 301–413. Springer, Berlin. · Zbl 0885.60061
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.