The van den Berg  Kesten Conjecture and Rudich's ConjectureCliff SmythRutgers University
February 23,

ABSTRACT


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 notx_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),We prove a correlation inequality that is in some sense dual to Reimer's inequality (a.k.a. the van den BergKesten conjecture). This inequality makes possible a short proof of Rudich's conjecture and other complexity theory results. This is joint work with Mike Saks and Jeff Kahn. 
Combinatorics Seminar, Mathematics Department, MIT, sara(atsign)math.mit.edu 

