Geodesic
On the convergence of probabilities of first-order sentences for recursive random graph models
Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ, Tome 494 (2020), pp. 35-37 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We study first-order zero–one law and the first-order convergence law for two recursive random graph models, namely, the uniform and preferential attachment models. In the uniform attachment model, a new vertex with $m$ edges chosen uniformly is added at every moment, while, in the preferential attachment model, the distribution of second ends of these edges is not uniform, but rather the probabilities are proportional to the degrees of the respective vertices.
Keywords: recursive random graphs, preferential attachment, first-order logic, zero–one laws. 
@article{DANMA_2020_494_a7,
     author = {M. E. Zhukovskii and Yu. Malyshkin},
     title = {On the convergence of probabilities of first-order sentences for recursive random graph models},
     journal = {Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleni\^a},
     pages = {35--37},
     year = {2020},
     volume = {494},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DANMA_2020_494_a7/}
}
TY  - JOUR
AU  - M. E. Zhukovskii
AU  - Yu. Malyshkin
TI  - On the convergence of probabilities of first-order sentences for recursive random graph models
JO  - Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ
PY  - 2020
SP  - 35
EP  - 37
VL  - 494
UR  - http://geodesic.mathdoc.fr/item/DANMA_2020_494_a7/
LA  - ru
ID  - DANMA_2020_494_a7
ER  - 
%0 Journal Article
%A M. E. Zhukovskii
%A Yu. Malyshkin
%T On the convergence of probabilities of first-order sentences for recursive random graph models
%J Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ
%D 2020
%P 35-37
%V 494
%U http://geodesic.mathdoc.fr/item/DANMA_2020_494_a7/
%G ru
%F DANMA_2020_494_a7
M. E. Zhukovskii; Yu. Malyshkin. On the convergence of probabilities of first-order sentences for recursive random graph models. Doklady Rossijskoj akademii nauk. Matematika, informatika, processy upravleniâ, Tome 494 (2020), pp. 35-37. http://geodesic.mathdoc.fr/item/DANMA_2020_494_a7/

[1] Glebskii Yu.V., Kogan D.I., Liogonkii M.I., Talanov V.A., “Ob'em i dolya vypolnimosti formuluzkogo ischisleniya predikatov”, Kibernetika, 2 (1969), 17–26 | MR

[2] Fagin R., “Probabilities on finite models”, J. Symbolic Logic, 41 (1976), 50–58 | DOI | MR | Zbl

[3] Vereschagin N.K., Shen A., Lektsii po matematicheskoi logike i teorii algoritmov, v. 2, Yazyki i ischisleniya, 4-e izd., ispr., MTsNMO, M., 2012, 240 pp.

[4] Libkin L., Elements of finite model theory, Texts in Theoretical Computer Science. An EATCS Ser, Springer-Verlag, B.–Heidelberg, 2004, 318 pp. | DOI | MR | Zbl

[5] Zhukovskii M.E., Raigorodskii A.M., “Sluchainye grafy: modeli i predelnye kharakteristiki”, UMN, 70:1 (2015), 35–88 | DOI | MR

[6] Spencer J.H., The Strange Logic of Random Graphs, Springer Verlag, 2001, 168 pp. | MR | Zbl

[7] Bollobás B., Riordan O., Spencer J., Tusnády G., “The Degree Sequence of a Scale-Free Random Graph Process”, Random structures and algorithms, 18:3 (2001), 279–290 | DOI | MR | Zbl

[8] Hofstag R., Random Graphs and Complex Networks, Cambridge University Press, Cambridge, 2016, 321 pp.

[9] Smythe R.T., Mahmoud H.M., “A survey of recursive trees”, Theory Prob. Math. Statist., 51 (1995), 1–27 | MR

[10] Ehrenfeucht A., “An application of games to the completeness problem for formalized theories”, Warszawa. Fund. Math., 49 (1960), 121–149 | MR

[11] McColm G.L., “MSO zero-one laws on random labelled acyclic graphs”, Discrete Mathematics, 254:1-3 (2002), 331–347 | DOI | MR | Zbl