COCOA Talk: 99-03

Speaker: Cliff Smyth

Let V = {x_1, x_2, x_3, ..., x_n} be a set of independent True/False
random variables, with Pr(x_i = True) = Pr(x_i = False) = 1/2.

A term on V is a conjunction of variables and negations of variables
in V.  For example, t_1 = x_1 && x_2 && not(x_3) and t_2 = x_3 && x_4
are both terms on V.

Let T = {t_1, t_2, ..., t_n} be a set of terms on V.  The neighborhood
of a term t_i is the set N_i of all terms in T that share a variable
with t_i.  In this context, x_i and its negation are considered to be
the same variable.  For example, if t_1 and t_2 are as before, N_1
contains both t_1 and t_2.

If S is a subset of T, let U(S) = Pr(exactly one term in S is True).
The following has been circulating unpublished for some years.

Conjecture (S. Rudich)

There exist a, b 0, such that for all pairs (V,T) as above,

U(T) 1 - a implies there exists an N_i so that U(N_i) b.

A short proof of this conjecture will be presented, utilizing the
Butterfly Theorem used by D. Reimer in the proof of the Van Den Berg -
Kesten Conjecture.

This is joint work with Jeff Kahn and Mike Saks.

DIMACS Home Page