Geodesic
Логика первого порядка на графах равномерного присоединения с заданной степенью вершин
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 3 (2024), pp. 33-41
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

В статье доказывается закон сходимости для логики первого порядка на случайных графах с равномерным присоединением вершин, в которых почти все вершины имеют одинаковую степень. В рассматриваемой модели вершины и ребра вводятся рекурсивно: в момент времени $m+1$ мы начинаем с полного графа на $m+1$ вершине. На шаге $n+1$ добавляется вершина $n+1$ вместе с $m$ ребрами, соединяющими новую вершину с $m$ вершинами, выбранными равновероятно из тех вершин из $1,\ldots,n$, степень которых меньше $d=2m$. Для доказательства закона мы описываем динамику классов логической эквивалентности случайного графа с помощью цепей Маркова. Закон сходимости следует из существования предельного распределения рассматриваемой цепи Маркова.
Mots-clés : равномерное присоединение, логика первого порядка, законы сходимости, Марковские цепи. 
@article{VTPMK_2024_3_a2,
     author = {Yu. A. Malyshkin},
     title = {{\CYRL}{\cyro}{\cyrg}{\cyri}{\cyrk}{\cyra} {\cyrp}{\cyre}{\cyrr}{\cyrv}{\cyro}{\cyrg}{\cyro} {\cyrp}{\cyro}{\cyrr}{\cyrya}{\cyrd}{\cyrk}{\cyra} {\cyrn}{\cyra} {\cyrg}{\cyrr}{\cyra}{\cyrf}{\cyra}{\cyrh} {\cyrr}{\cyra}{\cyrv}{\cyrn}{\cyro}{\cyrm}{\cyre}{\cyrr}{\cyrn}{\cyro}{\cyrg}{\cyro} {\cyrp}{\cyrr}{\cyri}{\cyrs}{\cyro}{\cyre}{\cyrd}{\cyri}{\cyrn}{\cyre}{\cyrn}{\cyri}{\cyrya} {\cyrs} {\cyrz}{\cyra}{\cyrd}{\cyra}{\cyrn}{\cyrn}{\cyro}{\cyrishrt} {\cyrs}{\cyrt}{\cyre}{\cyrp}{\cyre}{\cyrn}{\cyrsftsn}{\cyryu} {\cyrv}{\cyre}{\cyrr}{\cyrsh}{\cyri}{\cyrn}},
     journal = {Vestnik Tverskogo gosudarstvennogo universiteta. Seri\^a Prikladna\^a matematika},
     pages = {33--41},
     year = {2024},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/VTPMK_2024_3_a2/}
}
TY  - JOUR
AU  - Yu. A. Malyshkin
TI  - Логика первого порядка на графах равномерного присоединения с заданной степенью вершин
JO  - Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
PY  - 2024
SP  - 33
EP  - 41
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/VTPMK_2024_3_a2/
LA  - en
ID  - VTPMK_2024_3_a2
ER  - 
%0 Journal Article
%A Yu. A. Malyshkin
%T Логика первого порядка на графах равномерного присоединения с заданной степенью вершин
%J Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika
%D 2024
%P 33-41
%N 3
%U http://geodesic.mathdoc.fr/item/VTPMK_2024_3_a2/
%G en
%F VTPMK_2024_3_a2
Yu. A. Malyshkin. Логика первого порядка на графах равномерного присоединения с заданной степенью вершин. Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 3 (2024), pp. 33-41. http://geodesic.mathdoc.fr/item/VTPMK_2024_3_a2/

[1] Grimmett G. R., Stirzaker D. R., Probability and Random Processes, Oxford University Press, 2001, 596 pp. | MR

[2] Haber S., Krivelevich M., “The logic of random regular graphs”, Journal of Combinatorial Theory, 1(3-4) (2010), 389–440 | MR | Zbl

[3] Heinig P., Muller T., Noy M., Taraz A., “Logical limit laws for minor-closed classes of graphs”, Journal of Combinatorial Theory, Series B, 130 (2018), 158–206 | DOI | MR | Zbl

[4] Libkin L., Elements of Finite Model Theory, Springer, Berlin, 2004, 314 pp. | MR | Zbl

[5] Malyshkin Y. A., Zhukovskii M. E., “MSO 0-1 law for recursive random trees”, Statistics and Probability Letters, 173 (2021), 109061 | DOI | MR | Zbl

[6] Malyshkin Y. A., Zhukovskii M. E., “$\gamma$-variable first-order logic of uniform attachment random graphs”, Discrete Mathematics, 345:5 (2022), 112802 | DOI | MR | Zbl

[7] Malyshkin Y. A., Zhukovskii M. E., Logical convergence laws via stochastic approximation and Markov processes, Preprint at https://arxiv.org/abs/2210.13437, 2022

[8] Malyshkin Y. A., “$\gamma$-variable first-order logic of preferential attachment random graphs”, Discrete Applied Mathematics, 314 (2022), 223–227 | DOI | MR | Zbl

[9] Shelah S., Spencer J. H., “Zero-one laws for sparse random graphs”, Journal of the American Mathematical Society, 1 (1988), 97–115 | DOI | MR | Zbl

[10] Spencer J. H., “Threshold spectra via the Ehrenfeucht game”, Discrete Applied Mathematics, 30 (1991), 235–252 | DOI | MR | Zbl

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

[12] Winkler P., “Random structures and zero-one laws”, Finite and Infinite Combinatorics in Sets and Logic, NATO Advanced Science Institute Series, eds. N.W. Sauer, R.E. Woodrow and B. Sands, Kluwer Academic Publishers, Dordrecht, 1993, 399–420 | MR | Zbl