Lesson 5

In many applications, the following version of the local lemma is more convenient to use, where the localizer function \(\Gamma\) is absent, and instead, there is simply a bound on the number of events each of our events depends on.

Theorem (symmetric version). Let \(\mathcal{A}=\{A_{1}, \dotsc, A_{n}\}\) be a set of events, and suppose the following two properties hold for some \(q>0\), an integer \(d\ge 1\), and each \(A \in \mathcal{A}\):

1. \(\Pr[A] \le q\);
2. \(A\) depends on at most \(d\) other events: there exists a set \(A \in \mathcal{S} \subseteq \mathcal{A}\) of mutually independent events of size at least \(n-d\).

Proof. Let \(eq(d+1) \le 1\). We can assume that we have a function \(\Gamma\) such that \(|\Gamma(A)|=d\) for each \(A \in \mathcal{A}\). Set \(p(A)=1/(d+1)\) for all \(A \in \mathcal{A}\). Then it is enough to verify that the condition \[q \le \frac{1}{d+1}\left(1-\frac{1}{d+1}\right)^{d} \ .\] holds. We will show that it holds. For \(d \neq 0\) we have \(1+1/d<e^{1/d}\). In other words, \(\frac{d+1}{d}<e^{1/d}\). Hence, \[\frac{d}{d+1}>\frac{1}{e^{1/d}}\ .\] Raise to the power of \(d\): \[\left(\frac{d}{d+1}\right)^{d} > \frac{1}{e} \ .\] Thus, \[\frac{1}{d+1}\left(1-\frac{1}{d+1}\right)^{d} > \frac{1}{(d+1)e}\ge q \ .\] Since \(e\ q(d+1) \le 1\), the required inequality is established.

Now suppose \(4qd \le 1\). Let us choose a function \(p \colon \mathcal{A} \to [0,1)\) such that the condition \(\Pr[A] \le p(A) \prod_{B \in \Gamma(A)}(1-p(B))\) holds.

For \(d=1\) it is enough to set \(p(A)=1/2\) (for all \(A \in \mathcal{A}\)). For \(d \ge 2\) set \(p(A)=\frac{1}{d}\). The inequality then transforms into this: \[q \le \frac{1}{d}\left(1-\frac{1}{d}\right)^{d} \ .\] This inequality is true because \((1-1/d)^{d} \ge 1/4\) for \(d \ge 2\).◼