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

Cliff Smyth

Rutgers University

February 23,
refreshments at 3:45pm


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.

We prove a correlation inequality that is in some sense dual to Reimer's inequality (a.k.a. the van den Berg-Kesten 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.

Speaker's Contact Info: csmyth(at-sign)

Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)

Page loaded on January 13, 2000 at 12:32 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.