## 2 A Motivating Problem and the Original LLL  
### Hypergraph 2-coloring  
Let \(H\) be a hypergraph, in which every hyperedge has at least \(k\geq 3\) vertices, and each hyperedge intersects at most \(d\) others. We ask that for what values of \(k\) and \(d\) can it be guaranteed that such a hypergraph is _2-colorable_--that is, we can color each vertex with one of two colors, such as red and blue, such that no hyperedge becomes monochromatic. To describe a solution attempt, let \(E_{1},\ldots,E_{n}\) be the hyperedges in \(H\). Consider a _random_ coloring--that is, for each vertex, flip a coin independently and, depending on the outcome, color the vertex red or blue. Let \(A_{i}\) denote the event that \(E_{i}\) is monochromatic. What we aim to achieve is that no hyperedge is monochromatic, which is expressed by the event \(C=\overline{A}_{1}\ldots\overline{A}_{n}\). If we can show \(\Pr(C)>0\), a 2-coloring of \(H\) must exist. To find the probability of \(C\), let us first estimate the probability of \(A_{i}\). If \(E_{i}\) has \(\ell_{i}\) vertices, then out of its \(2^{\ell_{i}}\) possible colorings, only two are monochromatic (the all-red and all-blue colorings). Therefore,  
\[\Pr(A_{i})\;=\;\Pr(E_{i}\text{ is monochromatic})\;=\;2/2^{\ell_{i}}\leq 2/2^{k}\;= \;2^{1-k}, \tag{1}\]  
where the inequality follows from \(\ell_{i}\geq k\). Then, (1) implies \(\Pr(\overline{A}_{i})\geq 1-2^{1-k}\). Now, if the events \(A_{i}\) were independent, we could argue that  
\[\Pr(C)\;=\;\Pr(\overline{A}_{1}\ldots\overline{A}_{n})\;=\;\Pr(\overline{A}_{ 1})\cdot\ldots\cdot\Pr(\overline{A}_{n})\geq(1-2^{1-k})^{n}>0 \tag{2}\]  
holds. It would mean that with positive probability no edge is monochromatic, so a 2-coloring of \(H\) must indeed exist. The problem with this argument is that the events \(A_{1},\ldots,A_{n}\) are _not_ independent whenever the hyperedges overlap. Consequently, the equality \(\Pr(\overline{A}_{1}\ldots\overline{A}_{n})\;=\;\Pr(\overline{A}_{1})\cdot \ldots\cdot\Pr(\overline{A}_{n})\) that we used in (2) generally does not hold. This is the critical point where the LLL provides invaluable help. Before going into formal details, let us informally display the core message of the lemma:  
**Key message of LLL. **_For any system \(A_{1},\ldots,A_{n}\) of events, in order for the conclusion \(\Pr(\overline{A}_{1}\ldots\overline{A}_{n})>0\) to hold, it is enough if the events are \"almost\" independent, in the sense that each one of them depends only on a limited number of others, provided that \(\Pr(A_{i})\) is small enough._  
Specifically, the historically first version of the lemma, proved in the paper [2] published by [PERSON] and [PERSON] in 1973, is the following claim:  
Lemma 1 (Lll--symmetric version, original form): _Let \(A_{1},\ldots,A_{n}\) be events such that each event is mutually independent of all the others, except at most \(d\geq 1\) of them. If_  
\[\Pr(A_{i})\;\leq\;\frac{1}{4d}\;\;\;\;\;\;(\forall i) \tag{3}\]  
_holds, then \(\Pr(\overline{A}_{1}\ldots\overline{A}_{n})>0\)._  
Let us apply it to the above-described problem of hypergraph 2-coloring. Each event \(A_{i}\) in the example depends only on those events \(A_{j}\) for which \(E_{i}\cap E_{j}\
eq\emptyset\), since we pick the color of each vertex independently. As each hyperedge intersects at most \(d\) others, \(A_{i}\) may depend on at most \(d\) other events. We know from (1) that \(\Pr(A_{i})\leq 2^{1-k}\). Therefore, if  
\[2^{1-k}\leq\frac{1}{4d} \tag{4}\]  
holds, then \(\Pr(A_{i})\leq 2^{1-k}\leq\frac{1}{4d}\) follows, so the inequality (3) is satisfied. As a result, Lemma 1 implies \(\Pr(\overline{A}_{1}\ldots\overline{A}_{n})>0\), which means that the desired 2-coloring must exist. Rearranging (4), we obtain the condition \(4d\leq 2^{k-1}\), or equivalently, \(d\leq 2^{k-3}\). Thus, by means of the LLL, we have proved the following:  
Theorem 1: _Let \(H\) be a hypergraph in which each hyperedge has at least \(k\geq 3\) vertices, and any hyperedge intersects at most \(d\) others.