一句话：证明稀疏随机图两份独立样本的一阶可区分量词深度取决于 α 的有理逼近，并给出上下界。
本文研究用一阶（FO）句子区分二项随机图 G(n,n^{-α}) 的两个独立样本的问题。Shelah 与 Spencer 证明，当 α∈(0,1) 为无理数时 G(n,n^{-α}) 满足 FO 零一律，因而任何固定 FO 句子都无法以渐近概率 1 区分两个样本；但区分所需句子的量词深度 k_α 可能随 n 增长。作者证明 k_α 取决于 α 能被有理数逼近的程度：对所有非 Liouville 的 α∈(0,1)，k_α=Ω(ln ln ln n) w.h.p.；存在无理 α 使 k_α 任意缓慢增长 w.h.p.；并对所有 α∈(0,1) 给出上界。证明核心技术是生成非对称严格平衡图的随机算法，以及研究随机扰动图对称群的新方法。
We study the problem of distinguishing between two independent samples [EQUATION], [EQUATION] of a binomial random graph G(n, p) by first order (FO) sentences. Shelah and Spencer proved that, for a constant α ∈ (0, 1), G(n, n−-α) obeys FO zero-one law if and only if α is irrational. Therefore, for irrational α ∈ (0, 1), any fixed FO sentence does not distinguish between [EQUATION] with asymptotical probability 1 (w.h.p.) as n → ∞. We show that the minimum quantifier depth kα of a FO sentence [EQUATION] distinguishing between [EQUATION] depends on how closely α can be approximated by rationals: • for all non-Liouville α ∈ (0, 1), kα = Ω(ln ln ln n) w.h.p.; • there are irrational α ∈ (0, 1) with kα that grow arbitrarily slowly w.h.p.; • [EQUATION] for all α ∈ (0, 1). The main ingredients in our proofs are a novel randomized algorithm that generates asymmetric strictly balanced graphs as well as a new method to study symmetry groups of randomly perturbed graphs.