Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2008 / B / 7

The general Lovász local lemma concerns events $A_1,\dots ,A_m$ with a dependency graph: each $A_i$ is independent of the sigma-algebra generated by all nonneighbouring events other than itself. If numbers $x_i\in [0,1)$ satisfythen $\mathbb{P}({\bigcap }_i{A}_i^c)\ge {\prod }_i(1-x_i)>0$.

Its symmetric form states that if $\mathbb{P}(A_i)\le q$, every dependency degree is at most $d$, and $eq(d+1)\le 1$, then there is positive probability that no event occurs. For $d\ge 1$, set all $x_i=1/(d+1)$. Sincewe have $x_i(1-x_i{)}^d\ge 1/[e(d+1)]\ge q$, so the general form applies. The displayed inequality follows from $d\log (1+1/d)\le 1$. When $d=0$, the events are mutually independent and each has probability below one, so their complements have positive joint probability directly.

Each row sum is a sum of $k$ independent random signs. For $s>0$, its moment generating function isFor example, $\log \cosh s\le s^2/2$ follows by integrating $\tanh s\le s$ for $s\ge 0$. Markov's inequality yields $\mathbb{P}(Y_j\ge t)\le \exp (-st+k{s}^2/2)$. Choosing $s=t/k$ gives $e^{-t^2/(2k)}$ for $t>0$. The distribution is symmetric, so the same bound applies to its negative tail. A union bound provesfor $t\ge 0$, including the trivial endpoint $t=0$.

Let $t=\sqrt{2k{\log }_e(6kr)}$ and define $A_j=\{|Y_j|\ge t\}$. The preceding estimate gives $\mathbb{P}(A_j)\le 1/(3kr)$. An event depends only on the $k$ signs in that row. Each such column occurs in at most $r-1$ other rows, so its dependency degree is at most $d=k(r-1)$. Events on disjoint sets of signs are independent even jointly, giving the required dependency graph.

For positive $k,r$,The symmetric Lovász local lemma therefore gives positive probability that no $A_j$ occurs. Such a sign vector satisfiesThe positive-parameter assumption is implicit in the printed square-root expression. If all rows are zero, all row sums vanish and no probabilistic construction is needed.