The van den Berg - Kesten Conjecture and Rudich's Conjecture

Let V = {x_1,...,x_n} be a set of independent true/false random variables. A literal is a variable or the negation of a variable in V. A term is a conjunction of literals. We say a term t contains the variable x_i if it contains x_i or not-x_i.

Let T = {t_1,...,t_m} be a set of terms. Write t_j ~ t_k if they contain a common variable. Thus, viewing t_i as the event that t_i is true, (T, ~) is a Lovasz dependency graph. Let N_i be the neighborhood of t_i in T, including t_i.

If S is a subset of T, let let Pr(S) = Pr( at least one term in S is true ) and U(S) = Pr( exactly one term in S is true ). The following conjecture was motivated by considerations in computational complexity.

Conjecture (Rudich, 1984): There exist epsilon, delta > 0 such that if T is any set of terms over any set of variables V (as above),

if U(T) >= 1-epsilon then for some N_i, Pr(N_i) >= delta.