04 Existence proofs

$P r (X \geq E [X]) > 0$ , $P r (X \leq E [X]) > 0$ .

For sparse dependency graphs

Aka Lovasz local lemma.

For Dependency graph with $P r (E_{i}) < p, 4 d p < 1$ : $P r (\cap \bar{E_{i}}) > 0$ .

Lovasz local lemma: general case: Dependency. graph G=(V,E), \ $x_{i} \in [0, 1]$ : $P r (E_{i}) \leq x_{i} \prod_{(i, j) \in E} (1 - x_{j})$ : $P r (\cap \bar{E_{i}}) \geq \prod_{i} (1 - x_{i}) > 0$

Threshold behavior

$X > 0$ : Second moment method: $P r (X = 0) \leq P r ((X - E [X])^{2} \geq (E [X])^{2})$ . Conditional expectation inequality for $\sum$ indicators: \ $P r (X > 0) \geq \sum_{i = 1}^{n} \frac{P r (X_{i} = 1)}{E [X | X_{i} = 1]}$ .

Explicit constructions

\tbc

Make Existence proofs

Design sample space, show $P r (E) > 0$ , maybe modify to get final object. Use Expectation argument. Make non-negative RV X, use Chebyshev to bound Pr(X=0). Make dependency graph, use Lovasz local lemma.