 Solution

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

Let

I_{i} = 1_{A_{i}}

and

X = \sum_{i} I_{i}

μ = \sum_{i} P (A_{i}), Δ = \sum_{i \neq = j E_{i} \cap E_{j} \neq = \emptyset} P (A_{i} \cap A_{j}) .

The dependency sum is over ordered pairs, so each unordered overlapping pair is counted twice. Disjoint prescribed edge sets give independence.

Order the events. For each

i

, let

B_{i}

be the event that all earlier events fail. Split it as

B_{i} = C_{i} \cap D_{i}

, where

C_{i}

excludes earlier events with edge sets disjoint from

E_{i}

, and

D_{i}

excludes the overlapping earlier events. These are down-sets. The event

A_{i}

is a principal up-set, and it is independent of

C_{i}

since their determining edge sets are disjoint.

If some

B_{i}

has probability zero the desired zero-event bound is immediate. Otherwise the allowed conditional correlation inequality gives

P (C_{i} \cap D_{i} ∣ A_{i}) \geq P (C_{i} ∣ A_{i}) P (D_{i} ∣ A_{i}) = P (C_{i}) P (D_{i} ∣ A_{i}) .

Since

P (B_{i}) \leq P (C_{i})

q_{i} := P (A_{i} ∣ B_{i}) \geq P (A_{i}) P (D_{i} ∣ A_{i}) \geq P (A_{i}) - \sum_{j < i E_{j} \cap E_{i} \neq = \emptyset} P (A_{i} \cap A_{j}) .

The last step is the union bound under conditioning on

A_{i}

. Zero-probability events may simply be omitted, and a certain event makes the target probability zero. Finally the sequential product and

1 - u \leq e^{- u}

give

P (X = 0) = \prod_{i} (1 - q_{i}) \leq exp (- \sum_{i} q_{i}) \leq e^{- μ + Δ/2} .

This proves the first Janson inequality with the dependency-sum convention explicit.

 New to topics? Read the docs here!