Let I be a finite index set and let B i , i # I, be events in a probability space. Let G be an undirected graph on vertex set I. Suppose that whenever J, K are disjoint subsets of I with no pairs j # J, k # K adjacent any Boolean expression of the B j , j # J is independent of any Boolean expression of the B k , k # K. In this case we call G a strong dependency graph for the events. We note that this is somewhat stronger than the notion of dependency graph used in the Lova sz Local Lemma and considerably stronger than making i, i $ adjacent whenever B i , B i $ were independent. We shall fix a particular dependency graph (in general G is not uniquely determined though in many instances there is a natural choice for G) and we shall write itj for i, j being adjacent in G.
Assume all Pr[B i ] p and that every i # G has deg(i) d. Further assume 4dp<1. To avoid trivialities we take d 1 so that p< 1 4 . Set
the sum over unordered pairs. Further set
Here we give an elementary proof of the following inequality of Suen [4].
Theorem. Under the above assumptions
Remarks. While we have quite deliberately emphasized the similarities, the above result provides an upper bound on Pr[ร i # I B i ] while the Lova sz Article No. TA982885 95 0097-3165ร98 25.00