Geodesic
On the Probability of the Occurrence of a Copy of a Fixed Graph in a Random Distance Graph
Matematičeskie zametki, Tome 92 (2012) no. 6, pp. 844-855.

Voir la notice de l'article provenant de la source Math-Net.Ru

The threshold probability of the occurrence of a copy of a balanced graph in a random distance graph is obtained. The technique used by P. Erdős and A. Rényi for determining the threshold probability for the classical random graph could not be applied in the model under consideration. In this connection, a new method for deriving estimates of the number of copies of a balanced graph in a complete distance graph is developed.
Keywords: random distance graph, complete distance graph, balanced graph, threshold probability, Erdős–Rényi theorem on threshold probability, Stirling's formula. 
@article{MZM_2012_92_6_a4,
     author = {M. E. Zhukovskii},
     title = {On the {Probability} of the {Occurrence} of a {Copy} of a {Fixed} {Graph} in a {Random} {Distance} {Graph}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {844--855},
     publisher = {mathdoc},
     volume = {92},
     number = {6},
     year = {2012},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2012_92_6_a4/}
}
TY  - JOUR
AU  - M. E. Zhukovskii
TI  - On the Probability of the Occurrence of a Copy of a Fixed Graph in a Random Distance Graph
JO  - Matematičeskie zametki
PY  - 2012
SP  - 844
EP  - 855
VL  - 92
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2012_92_6_a4/
LA  - ru
ID  - MZM_2012_92_6_a4
ER  - 
%0 Journal Article
%A M. E. Zhukovskii
%T On the Probability of the Occurrence of a Copy of a Fixed Graph in a Random Distance Graph
%J Matematičeskie zametki
%D 2012
%P 844-855
%V 92
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2012_92_6_a4/
%G ru
%F MZM_2012_92_6_a4
M. E. Zhukovskii. On the Probability of the Occurrence of a Copy of a Fixed Graph in a Random Distance Graph. Matematičeskie zametki, Tome 92 (2012) no. 6, pp. 844-855. http://geodesic.mathdoc.fr/item/MZM_2012_92_6_a4/

[1] P. Erdős, A. Rényi, “On the evolution of random graphs”, Magyar Tud. Akad. Mat. Kutató Int. Közl., 5 (1960), 17–61 | MR | Zbl

[2] V. F. Kolchin, Sluchainye grafy, Fizmatlit, M., 2004 | MR | Zbl

[3] B. Bollobás, Random Graphs, Cambridge Stud. Adv. Math., 73, Cambridge Univ. Press, Cambridge, 2001 | MR | Zbl

[4] S. Janson, T. Łuczak, A. Rucinski, Random Graphs, Wiley-Intersci. Ser. Discrete Math. Optim., Wiley, New York, 2000 | MR | Zbl

[5] N. Alon, Dzh. Spenser, Veroyatnostnyi metod, Binom. Laboratoriya znanii, M., 2007 | MR | Zbl

[6] K. Schürger, “Limit theorems for complete subgraphs of random graphs”, Period. Math. Hungar., 10:1 (1979), 47–53 | DOI | MR | Zbl

[7] Z. Palka, “On the number of vertices of given degree in a random graph”, J. Graph Theory, 8:1 (1984), 167–170 | DOI | MR | Zbl

[8] A. D. Barbour, “Poisson convergence and random graphs”, Math. Proc. Cambridge Philos. Soc., 92:2 (1982), 349–359 | DOI | MR | Zbl

[9] S. Janson, T. Łuczak, A. Ruciński, “An exponential bound for the probability of nonexistence of a specified subgraph in a random graph”, Random Graphs '87 (Poznań, 1987), John Wiley Sons, Chichester, 1987, 73–87 | MR | Zbl

[10] M. E. Zhukovskii, “Oslablennyi zakon “nulya ili edinitsy” dlya sluchainykh distantsionnykh grafov”, Vestn. RUDN, 2:1 (2010), 11–25

[11] M. E. Zhukovskii, “Oslablennyi zakon nulya ili edinitsy dlya sluchainykh distantsionnykh grafov”, DAN, 430:3 (2010), 314–317 | MR | Zbl

[12] M. E. Zhukovskii, “Oslablennyi zakon nulya ili edinitsy dlya sluchainykh distantsionnykh grafov”, TVP, 55:2 (2010), 344–349 | DOI | MR

[13] K. A. Mikhailov, A. M. Raigorodskii, “O chislakh Ramseya dlya polnykh distantsionnykh grafov s vershinami v $\{0,1\}^n$”, Matem. sb., 200:12 (2009), 63–80 | DOI | MR

[14] A. M. Raigorodskii, “Problema Borsuka i khromaticheskie chisla nekotorykh metricheskikh prostranstv”, UMN, 56:1 (2001), 107–146 | DOI | MR | Zbl

[15] A. M. Raigorodskii, Lineino-algebraicheskii metod v kombinatorike, MTsNMO, M., 2007