Solution

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

For events with a dependency graph, assume each event is independent of the sigma-algebra generated by its nonneighbours. If numbers satisfy , the general Lovász local lemma gives
The symmetric version says that if every event has probability at most , the dependency graph has maximum degree at most , and , then none occurs with positive probability. For , set . Since , the general condition follows from the symmetric numerical hypothesis. The logarithmic inequality proves that estimate. When , the events are mutually independent and each has probability below one, so the conclusion is immediate. This is the intended implication from the general to the symmetric form; the source repeats the word symmetric in its final clause.

New to topics? Read the docs here!