×

On the number of isolated vertices in a growing random graph. (English) Zbl 1288.60010

Summary: This paper studies the properties of the number of isolated vertices in a random graph where vertices arrive one-by-one at times 1,2,…. They are connected by edges to the previous vertices independently with the same probability. Assuming that the probability of an edge tends to zero, we establish the asymptotics of large, normal, and moderate deviations for the stochastic process of the number of the isolated vertices considered at times inversely proportional to that probability. In addition, we identify the most likely trajectory for that stochastic process to follow conditioned on the event that at a large time the graph is found with a large number of isolated vertices.

MSC:

60C05 Combinatorial probability
05C80 Random graphs (graph-theoretic aspects)
60G99 Stochastic processes
60F10 Large deviations
60F17 Functional limit theorems; invariance principles
PDFBibTeX XMLCite
Full Text: DOI Euclid

References:

[1] A.D. Barbour, M. Karoński and A. Ruciński, A central limit theorem for decomposable random variables with applications to random graphs , J. Combin. Theor. 47 (1989), 125-145. · Zbl 0689.05042 · doi:10.1016/0095-8956(89)90014-2
[2] B. Bollobás, Random graphs , 2nd edition, Cambridge University Press, Cambridge, 2001.
[3] L. Cesari, Optimization - Theory and applications , Appl. Math. 17 Springer-Verlag, New York, 1983. · Zbl 0506.49001
[4] B. Dacorogna, Direct methods in the calculus of variations , Appl. Math. Sci. 78 , Springer, New York, 2008. · Zbl 1140.49001
[5] M.I. Freidlin and A.D. Wentzell, Random perturbations of dynamical systems , 2nd edition, Springer, New York, 1998. · Zbl 0922.60006
[6] E.N. Gilbert, Random graphs , Ann. Math. Stat. 30 (1959), 1141-1144. · Zbl 0168.40801 · doi:10.1214/aoms/1177706098
[7] J. Jacod and A.N. Shiryaev, Limit theorems for stochastic processes , Grundl. Math. Wiss. 288 (2003), Springer-Verlag, Berlin. · Zbl 1018.60002
[8] S. Janson, Orthogonal decompositions and functional limit theorems for random graph statistics , Mem. Amer. Math. Soc. 111 (1994), vi+78. · Zbl 0810.05001 · doi:10.1090/memo/0534
[9] —, The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph , Random Struct. Algor. 7 (1995), 337-355. · Zbl 0844.05085 · doi:10.1002/rsa.3240070406
[10] S. Janson, T. Łuczak and A. Ruciński, Random graphs , Wiley, New York, 2000.
[11] A.H. Joarder and M. Mahmood, An inductive derivation of Stirling numbers of the second kind and their applications in statistics , J. Appl. Math. Dec. Sci. 1 (1997), 151-157. · Zbl 0910.62015 · doi:10.1155/S1173912697000138
[12] V.F. Kolchin, Random graphs , Cambridge University Press, Cambridge, 1999. · Zbl 0918.05001
[13] W. Kordecki, Normal approximation and isolated vertices in random graphs , in Random graphs , Wiley, Chichester, 1990. · Zbl 0741.05063
[14] R.Sh. Liptser and A.N. Shiryayev, Theory of Martingales , Kluwer, Dordrecht, 1989. · Zbl 0728.60048
[15] N. O’Connell, Some large deviation results for sparse random graphs , Prob. Theor. Rel. Fields 110 (1998), 277-285. · Zbl 0927.60041 · doi:10.1007/s004400050149
[16] B. Pittel, On tree census and the giant component in sparse random graphs , Random Struct. Algor. 1 (1990), 311-341. · Zbl 0747.05080 · doi:10.1002/rsa.3240010306
[17] A. Puhalskii, Large deviations and idempotent probability , Chapman & Hall, CRC, Boca Raton, 2001. · Zbl 0983.60003
[18] Y. Punkla and N. Chaidee, Normal approximation of number of isolated vertices in a random graph , Thai J. Math. 4 (2006), 1-10. · Zbl 1158.60339
[19] J.M. Steele, Le Cam’s inequality and Poisson approximations , Amer. Math. Month. 101 (1994), 48-54. · Zbl 0802.60019 · doi:10.2307/2325124
[20] R. Vinter, Optimal control , Syst. Contr.: Found. Appl., Birkhäuser, Boston, MA, 2000. \noindentstyle
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.