MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Log-supermodular distributions over subsets of Boolean vectors

Suppose that two subsets $A, B\subseteq \{0, 1\}^n$ are such that every pair of vectors $x \in A\cap B$ and $y\in \bar{A}\cap\bar{B}$ satisfies one of the following two conditions:

• $x \land y \in A - B$ and $x \lor y \in B - A$;
• $x \land y \in B - A$ and $x \lor y \in A - B$.

Does this imply that for all log-supermodular distributions $P$ over $\{0, 1\}^n$ we have $P[A\cap B] \leq P[A]\,P[B]$? A probability distribution $P$ is called log-supermodular when $\forall x, y \in \{0, 1\}^n$ we have $P(x)\,P(y) \leq P(x\land y)\,P(x\lor y).$ Here “$\land$” and “$\lor$” are bitwise logical operations AND and OR.

This slightly resembles the Four Functions Theorem by Ahlswede and Daykin. I'd guess the answer is No, but do you have a counterexample? Motivation: this paper, Section 5.2

-
 Put in the extra backslashes to make the braces appear (markdown has a few quirks). – Zev Chonoles Feb 4 2011 at 3:32