7. 性能测试

我们正在寻找一种有效的随机算法来区分 $\text{triangle}-\text{free}$ 的大图和 $ϵ$ - 远离 $\text{triangle}-\text{free}$ 的图. 我们说一个图是 $ϵ$ - 远离属性 $\mathcal{P}$ 的, 如果为了获得属性 $\mathcal{P}$ 需要改变 (添加或删除) 的最小边数大于 $ϵn^2$. 我们给出算法如下.

命题 7.1 (算法). 对顶点的随机三元组进行采样, 并检查它们是否形成三角形. 重复 $C(ϵ)$ 次, 如果没有找到三角形, 则返回该图是 $\text{triangle}-\text{free}$ 的. 否则, 返回该图是 $ϵ$ - 远离 $\text{triangle}-\text{free}$ 的.

定理 7.2. 对于任意常数 $ϵ>0$, 存在一个常数 $C(ϵ)$, 使得算法 7.1 给出正确答案的概率大于 $\frac{2}{3}$.

证明. 如果图形 $G$ 是 $\text{triangle}-\text{free}$ 的, 则算法总是成功的, 因为没有采样的三元组会形成三角形. 如果 $G$ 是 $ϵ$ - 远离 $\text{triangle}-\text{free}$ 的, 那么根据三角形删除引理, $G$ 至少有 $\delta n^3$ 个三角形, 其中 $\delta =\delta (ϵ)$ 来自三角形删除引理 (定理 2.0.4) . 我们固定样本数为 $C(ϵ)=\frac{1}{\delta }$. 算法失败的概率等于我们完全没有对三角形进行采样的概率, 由于每个样本是独立挑选的, 这个概率是$${\left(1-\frac{\delta n^3}{\left(\genfrac{}{}{0ex}{}{n}{3}\right)}\right)}^{1/\delta }\le (1-6\delta {)}^{1/\delta }\le e^{-6}$$

$\square$

到目前为止, 我们已经看到有一个采样算法可以测试一个图是 $\text{triangle}-\text{free}$ 的还是 $ϵ$ -远离 $\text{triangle}-\text{free}$ 的. 我们能找到任何其他可测试的属性吗? 更确切地说, 对于哪些属性 $\mathcal{P}$ 有一种算法可以确定图 $G$ 处于两种情况中的哪一种? (要么具有属性 $\mathcal{P}$ 要么是 $ϵ$ - 远离属性 $\mathcal{P}$) . 特别的, 对于哪些图可以轻易检测出结果, 换句话说, 仅通过采样 $k=O(1)$ 个顶点就知道答案?

如果某属性在删除顶点后仍然保持, 我们称该属性是可遗传的. 具有遗传特性的一些例子是 $H-\text{free}$ 、平面性 ¹、$\text{induced}-H-\text{free}$ 、$3$-可着色和完美图 ². 无限版本删除引理 (定理 6.0.5) 意味着每个遗传属性都可以轻易检测出结果, 结果为满足属性或者不满足属性. 我们选择 $\mathcal{H}$ 作为所有不具有 $\mathcal{P}$ 属性的图的族. 注意对于遗传属性 $\mathcal{P}$, 没有 $\mathcal{P}$ 属性意味着不包含任何具有 $\mathcal{P}$ 属性的图. 这也解释了为什么这种单边检测方法不适用于检测非遗传属性. 事实上, 非遗传属性几乎都无法轻易检测出来.