论文标题
一阶逻辑可区分随机图的非常清晰的阈值
A very sharp threshold for first order logic distinguishability of random graphs
论文作者
论文摘要
在本文中，我们找到了一个整数$ h = h（n）$，以使一阶句子的最小变量数量区分两个独立的均匀分布的大小$ n $的独立分布的随机图，而渐近可能性最大的可能性$ \ frac {1} {1} {4} {4} {4} -o（1）$属于$ \ $ \ \ \ f \ h，h，h，h，h，h，h，h，h，h，h，h，h，h，h，h，h，h，h，h，h，h，h，h，h，h，h，h，h，h，h的）我们还证明，最小（随机）$ k $，因此，具有$ k $变量的第一阶句子可以区分两个独立的随机图，属于$ \ {h，h+1，h+1，h+2 \} $，概率$ 1-o（1）$。
In this paper we find an integer $h=h(n)$ such that the minimum number of variables of a first order sentence that distinguishes between two independent uniformly distributed random graphs of size $n$ with the asymptotically largest possible probability $\frac{1}{4}-o(1)$ belongs to $\{h,h+1,h+2,h+3\}$. We also prove that the minimum (random) $k$ such that two independent random graphs are distinguishable by a first order sentence with $k$ variables belongs to $\{h,h+1,h+2\}$ with probability $1-o(1)$.
