Let $H=(V,E)$ be a hypergraph with the property that each edge has at least $k \ge 2$ vertices. Show that if for each edge $e$ of $H(E)$ holds
$$ 8 \sum_{j \ge k} \frac{d_{e,j}}{2^j} \le 1$$
where $d_{e,j}$ is the number of edges of size $j$ intersecting $e$, then $H$ is $2$-colorable (i.e. there exists a $2$-coloring of $H(V)$ such that no edge of $H(E)$ is monochromatic).
I do not see how to do this. I realise that by assumption of $k \ge 2$ we can rewrite the sum into
$$ \sum_{j \ge k} \frac{d_{e,j}}{2^{j-2}} \le \frac{1}{2} $$
, but I do not see how to go on from there. Could you please give me a hint?
Edit: In class we have just done Lovász local lemma (the asymmetric case as Wikipedia calls it).
Best Answer
There is a less well-known "intermediate case" of the local lemma which guarantees the same thing as always (that $\overline A_1 \land \dots \land \overline A_n$ occurs with positive probability) under the hypothesis that $$\sum_{B \in \Gamma(A)} \Pr[B] \le \frac14.$$ Here, $\Gamma(A)$ denotes the neighbors of $A$ in the dependency graph.
I call this the "intermediate case" of the lemma because it adds a moderate amount of complexity to the symmetric version (our events can now have different probabilities) without the extreme complexity of requiring us to choose a weight for every event. We can prove the "intermediate case" from the asymmetric case by setting the weight $x(A)$ to be $2 \cdot \Pr[A]$ for every event $A$, and using the inequality $$\prod_{i=1}^n (1 - x_i) \ge 1 - \sum_{i=1}^n x_i$$ which is valid whenever $x_i \ge 0$ for all $i$, and in particular in our case where $x_i \in [0,1)$ for all $i$.
The condition $$8 \sum_{j \ge k} \frac{d_{e,j}}{2^j} \le 1 \iff \sum_{j \ge k} \frac{d_{e,j}}{2^{j-1}} \le \frac14$$ is exactly the condition we want to check for this version of the local lemma; we just have to check that our bad events have the correct probabilities and the correct dependencies to get this condition.