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

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.