 Solution

ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2009/b/6/a/ii/solution

0 \leq x_{i} < 1

with

P (A_{i}) \leq x_{i} \prod_{j \in Γ^{+} (i)} (1 - x_{j})

for every index, then

P (⋂_{i} A_{i}^{c}) \geq \prod_{i} (1 - x_{i}) > 0.

For maximum out-degree

d \geq 1

, take every

x_{i} = 1/ (d + 1)

. Since

(1 - \frac{1}{d + 1})^{d} = (1 + \frac{1}{d})^{- d} \geq e^{- 1},

one has

x_{i} (1 - x_{i})^{d} \geq 1/ [e (d + 1)] \geq p

. Fewer than

d

outgoing neighbours only increases the product, so the hypothesis is satisfied whenever

e p (d + 1) \leq 1

d = 0

, take

x_{i} = p < 1

; the neighbour products are empty and equal one. This separately covers the case in which

1/ (d + 1)

would equal the forbidden value one. Thus the symmetric local lemma follows in every case.

 New to topics? Read the docs here!