チャゼルの矛盾本：貪欲な方法

Question

バーナード・チャゼルの本で 不一致方法, 、それです 著者のウェブサイトからPDFとして無料で入手可能, 、読者による思考を必要とする最初の声明（定理1の直前）は、単純な確率引数によって取得されます。残念ながら、私は意図した議論に従うことができません。誰かが私を啓発できますか？

ここで$ chi（s_i）= sum_ {v in s_i} chi（v）$は 不一致 各要素に重みを割り当てる関数$ chi $に関して、セット$ s_i $の。

設定されたシステム$（v、s）$、$ | v | = n $ and $ | s | = m $、ランダムな着色$ chi $を選択します。つまり、$ v_j $ごとに、「color」$ chi（v_j）$が$ {-1,1 でランダムに、均一に、そして独立して選択されることを意味します。 } $。 $ s_i $はそうだと言います 悪い $ | chi（s_i）|の場合> sqrt {2 | s_i | ln（2m）} $。 Chernoff's Boundによると、すぐに$$ pr [s_i text {is bad}] < frac {1} {m}; $$を導き出します。

そして今、私が従わないビット：

したがって、ゼロ以外の確率では、$ s_i $は悪いことはありません。

$ m $のイベント「$ s_i $が悪くない」が相互に独立している場合、これは明らかに保持されます。また、の形式で保持されます LovászLocal Lemma これらのイベントがハイパーグラフのエッジ（$ 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 mid i = 1,2、 dots、m } $、$ pr [ text {some} s_i text {is bad}] <1 $、$ pr [ text {no} s_i text {is bad}]> 0 $ 。