Chazelle的差异书：贪婪的方法

Question

在伯纳德·查泽尔（Bernard Chazelle）的书中 差异方法, ，那是 从作者网站免费获得为PDF, ，通过简单的概率参数获得了读者（在定理1之前的第3页）中需要思考的第一个语句。不幸的是，我没有遵循预期的论点。有人可以启发我吗？

这里$ chi（s_i）= sum_ {v in s_i} chi（v）$是 差异 相对于函数$ chi $的集合$ s_i $，该$将权重分配给每个元素。

给定设置系统$（v，s）$，带有$ | v | = n $和$ | s | = m $，选择一个随机着色$ chi $，这意味着对于每个$ v_j $，“ color” $ chi（v_j）$是随机，均匀和独立选择的，以$ { - 1,1 } $。我们说$ s_i $是 坏的 如果$ | chi（s_i）| > sqrt {2 | s_i | ln（2m）} $。由Chernoff的Bound，我们立即得出$$ pr [s_i text {is bad}] < frac {1} {m} {m}; $$

现在我不关注的一点：

因此，对于非零概率，没有$ s_i $不好。

显然，如果“ $ s_i $不错”是相互独立的，则可以保持这一点。它也以一种形式 Lovász本地引理 如果这些事件形成了“足够好”的超图（以$ v $为顶点）的边缘。但是我不明白为什么在每种情况下都立即显而易见，正如作者似乎所暗示的那样。如果$ n $个体值$ chi（v_j）$是IID，那么我根本看不到$ m $ events“ $ s_i $不好，而且他们似乎并不是IID。

我想念什么？

任何反例都必须相当大（$ | s_i | $的$ M $指数大小），因此我确实相信该声明。但是我希望有令人信服的证据或指向其他参考的指针。

Answer 1

我的监督是$ | s | = m $，因此有“ $ s_i $不好”的$ m $事件。然后是$ pr [ cup_ {i = 1}^m a_i] le sum_ {i = 1}^m pr [a_i] $用于任何事件$ {a_i 中部i = 1,2， 点，m } $，它遵循$ pr [ text {some} s_i text {is bad}] <1 $，因此$ pr [ text {no} s_i text {is bad}> 0 $ 0 $ 。