Книга расхождений Шазель: жадный метод

Question

В книге Бернарда Шазель Метод расхождения, который Доступно бесплатно как PDF с сайта автора, Самое первое утверждение, требующее продуманности читателем (на стр. 3, непосредственно перед теоремой 1), получено с помощью простого аргумента вероятности. К сожалению, я не могу следовать предполагаемому аргументу. Может ли кто -нибудь просветить меня?

Здесь $ chi (s_i) = sum_ {v in s_i} chi (v) $ несоответствие из набора $ s_i $ в отношении функции $ chi $, которая назначает веса каждому элементу.

Учитывая установленную систему $ (v, s) $, с $ | V | = n $ и $ | s | = M $, выберите случайную окраску $ chi $, что означает, что для каждого $ v_j $, «цвет» $ chi (v_j) $ выбирается случайным образом, равномерно и независимо, в $ {-1,1 } $. Мы говорим, что $ s_i $ Плохо Если $ | chi (s_i) | > sqrt {2 | s_i | ln (2m)} $. By Chernoff's Bound, мы сразу же вы получаете $$ PR [S_I Text {Is Bad}] < frac {1} {M}; $$

А теперь чуть не следую:

Следовательно, с ненулевой вероятностью нет $ s_i $ плохо.

Очевидно, что это содержится, если события $ M $ "$ s_i $ не плохо", взаимозависимы. Он также имеет форму Ловаш Лемма Если эти события образуют края гиперграфа (с $ V $ как вершины), это «достаточно приятно». Но я не понимаю, почему это сразу очевидно в каждом случае, как подразумевает автор. Если индивидуальные значения $ n $ $ chi (v_j) $ iid, то я просто не вижу, чтобы события $ m $ "$ s_i $ не плохие" обязательно имеют достаточно хорошую форму для использования вероятностного метода , и они, конечно, не кажутся IID.

Что мне не хватает?

Любой контрпример должен быть довольно большим (с размером $ M $ экспоненциализированной в $ | S_i | $), поэтому я временно верю в заявление. Но я хотел бы убедительное доказательство или указатель на другую ссылку.

Answer 1

Мой надзор был, что $ | s | = M $, так что есть события $ M $ в форме "$ s_i $ плохо". Затем, так как $ 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 {некоторые} s_i text {is bad}] <1 $, так что $ pr [ text {no} s_i text {is bad}]> 0 $ Анкет