Critical random graphs: Diameter and mixing time. (English) Zbl 1160.05053

The mixing time of a random walk on a graph is defined as the waiting time \(t\) for closeness between the t-step transition probabilities and the stationary probabilities. For a random graph \(G(n,p)\), its largest connected component \(C\) and the mixing time of a random walk on \(C\) are investigated. The diameter of \(C\) and the mixing time are specified for \(p\) in the vicinity of \(1/n\). Generalizations to graphs with bounded degrees are also considered.


05C80 Random graphs (graph-theoretic aspects)
82B43 Percolation
60C05 Combinatorial probability
Full Text: DOI arXiv


[1] Aldous, D. (1997). Brownian excursions, critical random graphs and the multiplicative coalescent. Ann. Probab. 25 812-854. · Zbl 0877.60010
[2] Aldous, D. and Fill, J. (2007). Reversible Markov Chains and Random Walks on Graphs . Available at http://www.stat.berkeley.edu/ aldous/RWG/book.html.
[3] Alon, N. and Spencer, J. H. (2000). The Probabilistic Method , 2nd ed. Wiley, New York. · Zbl 0996.05001
[4] Barlow, M. and Kumagai, T. (2006). Random walk on the incipient infinite cluster on trees. Available at http://www.arxiv.org/abs/math.PR/0503118. · Zbl 1110.60090
[5] Benjamini, I., Kozma, G. and Wormald, N. (2006). The mixing time of the giant component of a random graph. Available at http://www.arxiv.org/abs/math.PR/0610459. · Zbl 1373.05172
[6] Bollobás, B., Janson, S. and Riordan, O. (2007). The phase transition in inhomogeneous random graphs. Random Structures Algoritms 31 3-122. · Zbl 1123.05083
[7] Borgs, C., Chayes, J. T., van der Hofstad, R., Slade, G. and Spencer, J. (2005). Random subgraphs of finite graphs: I. The scaling window under the triangle condition. Random Structures Algoritms 27 137-184. · Zbl 1076.05071
[8] Chandra, A. K., Raghavan, P., Ruzzo, W. L. and Smolensky, R. (1989). The electrical resistance of a graph captures its commute and cover times. Proc. Twenty-First ACM Symposium on Theory of Computing 574-586. ACM Press, New York. · Zbl 0905.60049
[9] Chung, F. and Lu, L. (2001). The diameter of random sparse graphs. Adv. in Appl. Math. 26 257-279. · Zbl 0977.05127
[10] Erdős, P. and Rényi, A. (1960). On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Kőzl. 5 17-61. · Zbl 0103.16301
[11] Fernholz, D. and Ramachandran, V. (2004). The diameter of sparse random graphs. Available at http://www.cs.utexas.edu/ fernholz/diam.ps. · Zbl 1129.05046
[12] Fountoulakis, N. and Reed, B. A. (2006). The evolution of the mixing rate. · Zbl 1147.60316
[13] van der Hofstad, R. and Luczak, M. (2006). Random subgraphs of the 2D Hamming graph: The supercritical phase. · Zbl 1188.05141
[14] Kolchin, V. F. (1986). Random Mappings . Optimization Software, New York. · Zbl 0605.60010
[15] Kesten, H., Ney, P. and Spitzer, F. (1966). The Galton-Watson process with mean one and finite variance. Theory Probab. Appl. 11 579-611. · Zbl 0158.35202
[16] Kolmogorov, A. N. (1938). On the solution of a problem in biology. Izv. NII Matem. Mekh. Tomskogo Univ. 2 7-12.
[17] Łuczak, T. (1998). Random trees and random graphs. Random Structures Algoritms 13 485-500. · Zbl 0959.05111
[18] Łuczak, T., Pittel, B. and Wierman, J. C. (1994). The structure of a random graph at the point of the phase transition. Trans. Amer. Math. Soc. 341 721-748. JSTOR: · Zbl 0807.05065
[19] Lyons, R. (1992). Random walks, capacity and percolation on trees. Ann. Probab. 20 2043-2088. · Zbl 0766.60091
[20] Lyons, R., Pemantle, R. and Peres, Y. (1995). Conceptual proofs of L log L criteria for mean behavior of branching processes. Ann. Probab. 23 1125-1138. · Zbl 0833.60085
[21] Nachmias, A. and Peres, Y. (2005). The critical random graph, with martingales. Israel J. Math. To appear. Available at http://www.arxiv.org/abs/math.PR/0512201. · Zbl 1215.05168
[22] Nachmias, A. and Peres, Y. (2006). Critical percolation on random regular graphs. Preprint. Available at http://www.arxiv.org/abs/0707.2839. · Zbl 1209.05228
[23] Nash-Williams, C. St. J. A. (1959). Random walk and electric currents in networks. Proc. Cambridge Philos. Soc. 55 181-194. · Zbl 0100.13602
[24] Peres, Y. (1999). Probability on trees: An introductory climb. École d’Été de Probabilités de Saint-Flour XXVII. Lecture Notes in Math. 1717 193-280. Springer, Berlin. · Zbl 0957.60001
[25] Tetali, P. (1991). Random walks and the effective resistance of networks. J. Theoret. Probab. 4 101-109. · Zbl 0722.60070
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.