## COCOA Talk: 99-03

## Butterflies and Rudich's Conjecture

### Speaker: Cliff Smyth

**
ABSTRACT
**

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