论文标题
限制随机稀疏图和超图的一阶属性的概率
Limiting probabilities of first order properties of random sparse graphs and hypergraphs
论文作者
论文摘要
令$ g_n $为稀疏制度中的二项式随机图$ g（n，p = c/n）$，这是众所周知的，在$ c = 1 $的情况下经历了相变。 Lynch（随机结构算法，1992年）表明，对于每个第一阶句子$ ϕ $，$ g_n $满足$ n \ to \ n to \ infty $的限制概率，并且它是$ c $的分析功能。在本文中，我们考虑$ \ overline {l_c} $ in $ [0,1] $ in $ g_n $的所有限制概率的设置$ l_c $的$ [0,1] $。我们表明，存在一个临界值$ C_0 \ oft0.93 $，因此$ \ overline {l_c} = [0,1] $当$ c \ ge c_0 $时，而$ \ overline {l_c} $在$ c <c_0 $时至少一个subsinteres。我们将这些结果扩展到随机的$ d $ - 均匀稀疏超图，其中HyperEdge的概率由$ P = C/N^{D-1} $给出。
Let $G_n$ be the binomial random graph $G(n,p=c/n)$ in the sparse regime, which as is well-known undergoes a phase transition at $c=1$. Lynch (Random Structures Algorithms, 1992) showed that for every first order sentence $ϕ$, the limiting probability that $G_n$ satisfies $ϕ$ as $n\to\infty$ exists, and moreover it is an analytic function of $c$. In this paper we consider the closure $\overline{L_c}$ in $[0,1]$ of the set $L_c$ of all limiting probabilities of first order sentences in $G_n$. We show that there exists a critical value $c_0 \approx0.93$ such that $\overline{L_c}= [0,1]$ when $c \ge c_0$, whereas $\overline{L_c}$ misses at least one subinterval when $c<c_0$. We extend these results to random $d$-uniform sparse hypergraphs, where the probability of a hyperedge is given by $p=c/n^{d-1}$.
