论文标题
具有给定度的均匀附件随机图的一阶逻辑
First-order logic of uniform attachment random graphs with a given degree
论文作者
论文摘要
在本文中，我们证明了均匀依恋随机图的一阶收敛定律，几乎所有顶点都具有相同的程度。在考虑的模型中，递归递归引入顶点和边缘：在$ m+1 $时，我们从$ m+1 $顶点的完整图开始。在步骤$ n+1 $下，顶点$ n+1 $与$ m $边缘一起加入新顶点，并从$ m $顶点从$ 1，\ ldots，n $的顶点均匀地选择，$ d = 2m $ d = 2M $。为了证明法律，我们使用马尔可夫链描述了随机图的逻辑等效类别的动力学。收敛定律遵循考虑的马尔可夫链的极限分布的存在。
In this paper, we prove the first-order convergence law for the uniform attachment random graph with almost all vertices having the same degree. In the considered model, vertices and edges are introduced recursively: at time $m+1$ we start with a complete graph on $m+1$ vertices. At step $n+1$ the vertex $n+1$ is introduced together with $m$ edges joining the new vertex with $m$ vertices chosen uniformly from those vertices of $1,\ldots,n$, whom degree is less then $d=2m$. To prove the law, we describe the dynamics of the logical equivalence class of the random graph using Markov chains. The convergence law follows from the existence of a limit distribution of the considered Markov chain.
