Lesson 2

Theorem (Erdős — Lovász, 1975; asymmetric version). Let \(\mathcal{A}=\{A_{1}, \dotsc, A_{n}\}\) be a set of events. Suppose there exist functions \(\Gamma \colon \mathcal{A} \to 2^{\mathcal{A}}\) and \(p \colon \mathcal{A} \to [0,1)\) with the following two properties, holding for all \(A \in \mathcal{A}\):

• \(\Gamma(A)\subseteq\mathcal{A}\setminus\{A\}\), and \(A\) is independent of the collection \(\mathcal{A}\setminus(\Gamma(A)\cup\{A\})\): for every \(\mathcal{S}\subseteq\mathcal{A}\setminus(\Gamma(A)\cup\{A\})\), \[\Pr\!\left[A\cap\bigcap_{B\in\mathcal{S}}\overline B\right]=\Pr[A]\Pr\!\left[\bigcap_{B\in\mathcal{S}}\overline B\right].\] The events in this collection need not be mutually independent.
• \(\Pr[A] \le p(A) \prod_{B \in \Gamma(A)}(1-p(B))\).

Then \[ \Pr\left[ \bigcap_{i \in [n]} \overline{A}_i\right] \ge \prod_{i \in [n]}(1-p(A_i))>0 \ . \]