稀疏随机图的一阶可区分性

《The Journal of Symbolic Logic》：FIRST-ORDER DISTINGUISHABILITY OF SPARSE RANDOM GRAPHS

　　我们研究了用一阶（FO）句子区分二项随机图 $G(n,p)$ 的两个独立样本 $\mathbf{G}_n^1, \mathbf{G}_n^2$ 的问题。Shelah和Spencer证明了，对于常数 $\alpha \in (0,1)$，$G(n,n^{-\alpha})$ 满足FO零一法则当且仅当 $\alpha$ 是无理数。因此，对于无理 $\alpha \in (0,1)$，任何固定的FO句子以渐近概率1无法区分 $\mathbf{G}_n^1, \mathbf{G}_n^2$（当 $n \to \infty$）。我们证明了区分 $\mathbf{G}_n^1, \mathbf{G}_n^2$ 的FO句子 $\varphi = \varphi(\mathbf{G}_n^1, \mathbf{G}_n^2)$ 的最小量词深度 $\mathbf{k}_\alpha$ 取决于 $\alpha$ 被有理数逼近的精度：- 对所有非刘维尔数 $\alpha \in (0,1)$，$\mathbf{k}_\alpha = \Omega(\ln\ln\ln n)$（以高概率）；- 存在无理数 $\alpha \in (0,1)$，使得 $\mathbf{k}_\alpha$ 的增长可以任意缓慢（以高概率）；- 对所有 $\alpha \in (0,1)$，$\mathbf{k}_\alpha = O_p\left(\frac{\ln n}{\ln \ln n}\right)$。我们证明中的主要工具包括：一种生成非对称严格平衡图的新随机算法，以及一种研究随机扰动图对称群的新方法。