Логика первого порядка на графах равномерного присоединения с заданной степенью вершин
Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 3 (2024), pp. 33-41
Voir la notice de l'article provenant de la source Math-Net.Ru
В статье доказывается закон сходимости для логики первого порядка на случайных графах с равномерным присоединением вершин, в которых почти все вершины имеют одинаковую степень. В рассматриваемой модели вершины и ребра вводятся рекурсивно: в момент времени $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},
publisher = {mathdoc},
number = {3},
year = {2024},
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 PB - mathdoc 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 %I mathdoc %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/