202311151411

Lovasz Local Lemma

$n$ bad events: $A_{1}, A_{2}, \dots, A_{n}$ , each can occur with probability $p_{i} \leq p < 1$ . So we know that we can avoid each event individually, we want to show that we can avoid all of them simultaneously. $P r [i = 1 ⋂ n \overset{ˉ}{A}_{i}] > 0$ If the events are independent, then $P r [i = 1 ⋂ n \overset{ˉ}{A}_{i}] \geq (1 - p)^{n} > 0$ .

LLL: If $A_{1}, A_{2}, \dots, A_{n}$ are events s.t. $P r [A_{i}] \leq p < 1 \forall i$ and each $A_{i}$ depends on at most $d$ $A_{j}$ s, and $e p (d + 1) \leq 1$ then $P r [i = 1 ⋂ n \overset{ˉ}{A}_{i}] > 0$ .

k-SAT

$ϕ = C_{1} \land C_{2} \land \dots \land C_{m}$ $n$ variables Let $a = (a_{1}, \dots, a_{n})$ be an assignment $A_{i} :$ Clause $C_{i}$ is not satisfied by $a$

Lemma: Any $k - S A T$ formula where each variable appears in at most $\frac{2 ^{k - 2}}{k}$ clauses is always satisfiable. Proof: $P r [A_{i}] = \frac{1}{2 ^{k}} = p$ , $d = 2^{k - 2}$ (each clause can share a variable with $\leq \frac{2 ^{k - 2}}{k} k$ clauses) $4 p d = \frac{4. 2 ^{k - 2}}{2 ^{k}} = 1$ By LLL, $P r [i = 1 ⋂ n \overset{ˉ}{A}_{i}] > 0$ . So there exists an assignment that satisfies all clauses.

🏠 No Place Like ~

Explorer

Lovasz Local Lemma

k-SAT

Proof of LLL

References

Graph View

Table of Contents

Backlinks