Stochastic processes in random graphs. (English) Zbl 1096.60008

Summary: We study the asymptotics of large, moderate and normal deviations for the connected components of the sparse random graph by the method of stochastic processes. We obtain the logarithmic asymptotics of large deviations of the joint distribution of the number of connected components, of the sizes of the giant components and of the numbers of the excess edges of the giant components. For the supercritical case, we obtain the asymptotics of normal deviations and the logarithmic asymptotics of large and moderate deviations of the joint distribution of the number of components, of the size of the largest component and of the number of the excess edges of the largest component. For the critical case, we obtain the logarithmic asymptotics of moderate deviations of the joint distribution of the sizes of connected components and of the numbers of the excess edges. Some related asymptotics are also established. The proofs of the large and moderate deviation asymptotics employ methods of idempotent probability theory. As a byproduct of the results, we provide some additional insight into the nature of phase transitions in sparse random graphs.


60C05 Combinatorial probability
05C80 Random graphs (graph-theoretic aspects)
60F05 Central limit and other weak theorems
60F10 Large deviations
60F17 Functional limit theorems; invariance principles
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] Alekseev, V. M., Tikhomirov, V. M. and Fomin, S. V. (1987). Optimal Control. Consultants Bureau, New York. · Zbl 0689.49001
[3] Aubin, J.-P. and Ekeland, I. (1984). Applied Nonlinear Analysis. Wiley, New York. · Zbl 0641.47066
[4] Barraez, D., Boucheron, S. and Fernandez de la Vega, W. (2000). On the fluctuations of the giant component. Combin. Probab. Comput. 9 287–304. · Zbl 0969.05054
[5] Bennett, C. and Sharpley, R. (1988). Interpolation of Operators . Academic Press, London. · Zbl 0647.46057
[6] Bollobás, B. (2001). Random Graphs , 2nd ed. Cambridge Univ. Press. · Zbl 0979.05003
[7] Bollobás, B., Grimmett, G. and Janson, S. (1996). The random-cluster model on the complete graph. Probab. Theory Related Fields 104 283–317. · Zbl 0846.05075
[8] Chaganty, N. R. (1997). Large deviations for joint distributions and statistical applications. Sankhyā Ser. A 59 147–166. · Zbl 0892.60041
[9] de Acosta, A. (2000). A general non-convex large deviation result with applications to stochastic equations. Probab. Theory Related Fields 118 483–521. · Zbl 0993.60028
[10] Dembo, A. and Zeitouni, O. (1998). Large Deviations Techniques and Applications , 2nd ed. Springer, New York. · Zbl 0896.60013
[11] DeVore, R. A. and Lorentz, G. G. (1993). Constructive Approximation . Springer, New York. · Zbl 0797.41016
[12] Ekeland, I. and Temam, R. (1976). Convex Analysis and Variational Problems . North-Holland, Amsterdam. · Zbl 0322.90046
[13] Ethier, S. N. and Kurtz, T. G. (1986). Markov Processes . Characterization and Convergence . Wiley, New York. · Zbl 0592.60049
[14] Freidlin, M. I. and Wentzell, A. D. (1998). Random Perturbations of Dynamical Systems , 2nd ed. Springer, New York. · Zbl 0922.60006
[15] Gärtner, J. (1977). On large deviations from an invariant measure. Teor. Veroyatnost. i Primenen. 22 27–42. (In Russian.)
[16] Ikeda, N. and Watanabe, S. (1989). Stochastic Differential Equations and Diffusion Processes , 2nd ed. North-Holland, Amsterdam. · Zbl 0684.60040
[17] Jacod, J. and Shiryaev, A. N. (1987). Limit Theorems for Stochastic Processes . Springer, New York. · Zbl 0635.60021
[18] Janson, S., Łuczak, T. and Ruciński, A. (2000). Random Graphs . Wiley, New York. · Zbl 0968.05003
[19] Kolchin, V. F. (1999). Random Graphs . Cambridge Univ. Press. · Zbl 0918.05001
[20] Krasnosel’skiĭ, M. A. and Rutickiĭ, J. B. (1961). Convex Functions and Orlicz Spaces . Translated from the first Russian edition by Leo F. Boron. Noordhoff, Groningen.
[21] Liptser, R. (1996). Large deviations for two scaled diffusions. Probab. Theory Related Fields 106 71–104. · Zbl 0855.60030
[22] Liptser, R., Spokoiny, V. and Veretennikov, A. Y. (2002). Freidlin–Wentzell type large deviations for smooth processes. Markov Process. Related Fields 8 611–636. · Zbl 1022.60076
[23] Liptser, R. S. and Shiryayev, A. N. (1989). Theory of Martingales . Kluwer, Dordrecht. · Zbl 0728.60048
[24] O’Connell, N. (1998). Some large deviation results for sparse random graphs. Probab. Theory Related Fields 110 277–285. · Zbl 0927.60041
[25] Pittel, B. (1990). On tree census and the giant component in sparse random graphs. Random Structures Algorithms 1 311–341. · Zbl 0747.05080
[26] Puhalskii, A. (1994). The method of stochastic exponentials for large deviations. Stochastic Process. Appl. 54 45–70. · Zbl 0812.60026
[27] Puhalskii, A. (1995). Large deviation analysis of the single server queue. Queueing Syst. Theory Appl. 21 5–66. · Zbl 0849.60083
[28] Puhalskii, A. (2001). Large Deviations and Idempotent Probability . Chapman and Hall, London. · Zbl 0983.60003
[29] Puhalskii, A. (2004). On some degenerate large deviation problems. Unpublished manuscript. · Zbl 1063.60031
[30] Stepanov, V. E. (1970a). On the probability of connectedness of the random graph \(\mathcal G_m(t)\). Teor. Veroyatnost. i Primenen . 15 56–68. (In Russian.) · Zbl 0213.45805
[31] Stepanov, V. E. (1970b). Phase transitions in random graphs. Teor. Veroyatnost. i Primenen. 15 200–216. (In Russian.) · Zbl 0225.90048
[32] Stepanov, V. E. (1972). Structure of the random graphs \(\mathcal G_m(x|h)\). Teor. Veroyatnost. i Primenen. 17 238–252. (In Russian.) · Zbl 0264.90048
[33] Whitt, W. (2002). Stochastic-Process Limits . Springer, New York. · Zbl 0993.60001
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.