 |
|
|
| | | | | |
|
|
|
|
|
Continuity of the percolation threshold in randomly grown graphs.
|
Tatyana S. Turova, Lund University, Sweden
|
Abstract
We consider various models of randomly grown graphs. In these models the vertices and the edges accumulate within time according to certain rules. We study a phase transition in these models along a parameter which refers to the mean life-time of an edge. Although deleting old edges in the uniformly grown graph changes abruptly the
properties of the model, we show that some of the macro-characteristics of the graph vary continuously. In particular, our results yield a lower bound for the size of the largest connected component of the uniformly grown graph.
|
Full text: PDF
Pages: 1036-1047
Published on: August 9, 2007
|
Bibliography
- Athreya, Krishna B.; Ney, Peter E. Branching processes. Die Grundlehren der mathematischen Wissenschaften, Band 196. Springer-Verlag, New York-Heidelberg, 1972. xi+287 pp. MR0373040 (51 #9242)
- Bollobás, Béla; Janson, Svante; Riordan, Oliver. The phase transition in the uniformly grown random graph has infinite order. Random Structures Algorithms 26 (2005), no. 1-2, 1--36. MR2116573 (2006a:05148)
- B. Bollobas, S. Janson, O. Riordan, The phase transition in inhomogeneous random graphs. Random Structures and Algorithms, to appear. (arXiv:math.PR/0504589)
- D.S. Callaway, J.E. Hopcroft, J.M. Kleinberg, M.E. J. Newman, and S. H. Strogatz, Are randomly grown graphs really random? Phys. Review E, 64 (2001), 041902.
- Durrett, Rick. Rigorous result for the CHKNS random graph model. Discrete random walks (Paris, 2003), 95--104 (electronic), Discrete Math. Theor. Comput. Sci. Proc., AC, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2003. MR2042377 (2005d:05133)
- Hammersley, J. M. Generalization of the fundamental theorem on sub-additive functions. Proc. Cambridge Philos. Soc. 58 1962 235--238. MR0137800 (25 #1249)
- Stanley, R.P. (1999). Enumerative combinatorics. Vol. 2. Cambridge Studies in Advanced Mathematics, Vol.62. Cambridge University Press, Cambridge. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.
- Söderberg, Bo. Properties of random graphs with hidden color. Phys. Rev. E (3) 68 (2003), no. 2, 026107, 12 pp. MR2010072 (2004h:82037)
- B. Soderberg, Random graphs with hidden color. Physical Review E 68, (2003) 015102.
- Söderberg, Bo. General formalism for inhomogeneous random graphs. Phys. Rev. E (3) 66 (2002), no. 6, 066121, 6 pp. MR1953933 (2003m:05194)
- Turova, Tatyana S. Long paths and cycles in dynamical graphs. J. Statist. Phys. 110 (2003), no. 1-2, 385--417. MR1966334 (2004b:60024)
- Turova, Tatyana S. Dynamical random graphs with memory. Phys. Rev. E (3) 65 (2002), no. 6, 066102, 9 pp. MR1920605 (2003e:60022)
- Turova, Tatyana S. Phase transitions in dynamical random graphs. J. Stat. Phys. 123 (2006), no. 5, 1007--1032. MR2258360 (2007f:05164)
|
|
|
|
|
|
|
|
| | | | |
Electronic Journal of Probability. ISSN: 1083-6489 |
|
Context