Abstract:
В статье доказывается закон сходимости для логики первого порядка на случайных графах с равномерным присоединением вершин, в которых почти все вершины имеют одинаковую степень. В рассматриваемой модели вершины и ребра вводятся рекурсивно: в момент времени $m+1$ мы начинаем с полного графа на $m+1$ вершине. На шаге $n+1$ добавляется вершина $n+1$ вместе с $m$ ребрами, соединяющими новую вершину с $m$ вершинами, выбранными равновероятно из тех вершин из $1,\ldots,n$, степень которых меньше $d=2m$. Для доказательства закона мы описываем динамику классов логической эквивалентности случайного графа с помощью цепей Маркова. Закон сходимости следует из существования предельного распределения рассматриваемой цепи Маркова.
Keywords:равномерное присоединение, логика первого порядка, законы сходимости, Марковские цепи.
Fulltext:
PDF file (473 kB)