×

A strong law of large numbers for random biased connected graphs. (English. Russian original) Zbl 1280.05121

Theor. Math. Phys. 172, No. 3, 1177-1186 (2012); translation from Teor. Mat. Fiz. 172, No. 3, 344-354 (2012).
Summary: We consider a class of random connected graphs with random vertices and random edges in which the randomness of the vertices is determined by a continuous probability distribution and the randomness of the edges is determined by a connection function. We derive a strong law of large numbers on the total lengths of all random edges for a random biased connected graph that is a generalization of a directed \(k\)-nearest-neighbor graph.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C40 Connectivity
60E15 Inequalities; stochastic orderings
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. Erdos and A. Rényi, Publ. Math. Debrecen, 6, 290–297 (1959).
[2] P. Erdos and A. Rényi, Publ. Math. Inst. Hung. Acad. Sci. Ser. A, 5, 17–61 (1960).
[3] P. Erdos and A. Rényi, Bull. Inst. Internat. Statist., 38, 343–347 (1961).
[4] Z. H. Xu and Y. Higuchi, Sci. China Ser. A (Chinese version), 42, 821–826 (2012).
[5] G. Grimmett, Percolation (Grundlehren Math. Wiss., Vol. 321, 2nd ed.), Springer, Berlin (1999). · Zbl 0926.60004
[6] B. Bollobás and O. Riordan, Percolation, Cambridge Univ. Press, Cambridge (2006).
[7] K. Kuulasmaa, J. Appl. Probab., 19, 745–758 (1982). · Zbl 0509.60094 · doi:10.2307/3213827
[8] Z. H. Xu and D. Han, Chinese J. Appl. Probab. Statist., 26, 649–661 (2010).
[9] M. D. Penrose, Random Geometric Graphs (Oxford Stud. Probab., Vol. 5), Oxford Univ. Press, Oxford (2003). · Zbl 1029.60007
[10] I. Benjamini and N. Berger, Random Structures Algorithms, 19, 102–111 (2001). · Zbl 0983.60099 · doi:10.1002/rsa.1022
[11] D. Coppersmith, D. Gamarnik, and M. Sviridenko, Random Structures Algorithms, 21, 1–13 (2002). · Zbl 1011.60086 · doi:10.1002/rsa.10042
[12] M. Biskup, Random Structures Algorithms, 39, 210–227 (2011). · Zbl 1228.05134 · doi:10.1002/rsa.20349
[13] M. D. Penrose, Stochastic Process. Appl., 85, 295–320 (2000). · Zbl 0997.60014 · doi:10.1016/S0304-4149(99)00080-0
[14] F. Xue and P. R. Kumar, Wireless Networks, 10, 169–181 (2004). · Zbl 02060502 · doi:10.1023/B:WINE.0000013081.09837.c0
[15] S. H. Teng and F. F. Yao, Algorithmica, 49, 192–211 (2007). · Zbl 1131.60089 · doi:10.1007/s00453-007-9040-7
[16] R. Meester and R. Roy, Continuum Percolation (Cambridge Tracts Math., Vol. 119), Cambridge Univ. Press, Cambridge (1996). · Zbl 0858.60092
[17] R. A. Dwyer, Comput. Geom., 5, 155–164 (1995). · Zbl 0838.68085 · doi:10.1016/0925-7721(94)00025-Q
[18] G. T. Toussaint, Pattern Recognition, 12, 261–268 (1980). · Zbl 0437.05050 · doi:10.1016/0031-3203(80)90066-7
[19] P. J. Bickel and L. Breiman, Ann. Probab., 11, 185–214 (1983). · Zbl 0502.62045 · doi:10.1214/aop/1176993668
[20] D. Evans and A. J. Jones, Proc. Roy. Soc. London A, 458, 2759–2799 (2002). · Zbl 1151.62349 · doi:10.1098/rspa.2002.1010
[21] N. Henze, Adv. Appl. Probab., 19, 873–895 (1987). · Zbl 0641.60039 · doi:10.2307/1427106
[22] P. Baldi and Y. Rinott, Ann. Probab., 17, 1646–1650 (1989). · Zbl 0691.60020 · doi:10.1214/aop/1176991178
[23] G. L. Miller, S. H. Teng, and S. Vavasis, ”A unified geometric approach to graph separators,” in: Proc. 32nd Annual Symposium on Foundations of Computer Science (1–4 October 1991, San Juan, Puerto Rico), IEEE Comput. Soc. Press, Los Alamitos, Calif. (1991), pp. 538–547.
[24] B. Efron and C. Stein, Ann. Statist., 9, 586–596 (1981). · Zbl 0481.62035 · doi:10.1214/aos/1176345462
[25] D. Evans, A. J. Jones, and W. M. Schmidt, Proc. Roy. Soc. London A, 458, 2839–2849 (2002). · Zbl 1054.60010 · doi:10.1098/rspa.2002.1011
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.