\documentclass[12pt]{article}
\usepackage{amssymb, amsmath, amsthm, epsf, epsfig, color}

\setlength{\oddsidemargin}{0in}
\setlength{\topmargin}{-.35in}
\addtolength{\textwidth}{1.23in}
\addtolength{\textheight}{1.5in}
\newcommand{\E}{{\mathbf E}}
\newlength{\originalbase}
\setlength{\originalbase}{\baselineskip}
\newcommand{\spacing}[1]{\setlength{\baselineskip}{#1\originalbase}}
\newcommand{\ep}{\varepsilon}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\nat}{\mathbb{N}}
\newcommand{\restr}{\! \upharpoonright \!}
\def\eps{\epsilon}

\begin{document}

\spacing{1.5}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{claim}{Claim}[theorem]
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{guess}[theorem]{Conjecture}
\newtheorem{conjecture}[theorem]{Conjecture}

\title{A Stronger Form of the Van den Berg-Kesten Inequality}

\author{Peter Winkler~\thanks{Dartmouth College, Hanover NH.
Research supported by NSF grant DMS-0901475.}}

\maketitle

\begin{abstract}
Let $Q^n := \{0,1\}^n$ be the discrete hypercube with
uniform probability distribution, and let $A$ and $B$ be
two ``up-events''---that is, subsets of $Q^n$ which are
closed under the operation of changing any coordinate of
an element from 0 to 1.  Let $B'$ be the down-event (necessarily
of the same probability as $B$) consisting of all $\{0,1\}$-complements
of elements of $B$.

The Van den Berg-Kesten inequality says that the probability that
$A$ and $B$ occur {\em disjointly} is no greater than the product
of their probabilities; symbolically, $\P(A \Box B) \le \P(A)\P(B)$.
Harris' inequality says that $\P(A \cap B') \le \P(A)\P(B')$;
which inequality is the stronger?

We show that $\P(A \Box B) \le \P(A \cap B')$,
characterizing the cases in which the inequality
is strict.  An example is given that arises naturally in Smirnov's
proof of conformal invariance for critical site percolation on the triangular grid.
\end{abstract}

\medskip

\section{Introduction}

The Van den Berg-Kesten inequality \cite{BK} and Harris' inequality \cite{H} are
fundamental facts about probability in a product space, both of which played important
roles in the development of percolation \cite{BR,G}.  Each has been vastly
generalized in more recent years: the former to the FKG inequality \cite{FKG}
and then the ``four-function theorem'' of Alswede and Daykin \cite{AD}; the latter,
to a theorem of Van den Berg and Fiebig \cite{BF} and then, spectacularly, to Reimer's
theorem \cite{R}.

At first glance, the two basic inequalities appear similar but not really comparable.
When applied to a pair of up-events $A$ and $B$, they run in opposite directions:
Harris' says that they are non-negatively correlated, that is, that $\P(A \cap B) \ge \P(A)\P(B)$,
while Van den Berg-Kesten says that when occurrences must be ``disjoint'' (see below for
definition), we get $\P(A \Box B) \le \P(A)\P(B)$.

Applied to an up-event $A$ and a down-event $D$, the inequalities are equivalent:
$A \cap D$ and $A \Box D$ are identical, since $A$ and $D$ can {\em only} occur disjointly,
and for opposing events---one up, one down---Harris' inequality reverses direction.

To set up Van den Berg-Kesten and Harris for a bake-off, we consider the uniform binary setting,
that is, the probability space $Q^n := \{0,1\}^n$ with uniform distribution.
This is an important special case in percolation theory, because the critical probabilities
for bond percolation on the square grid and for site percolation on the triangular grid
are both equal to $\frac12$; moreover, it was known \cite{BF} long before Reimer came along that the
general Van den Berg-Kesten conjecture could be reduced to the uniform binary case.
The key consequence of our assumption is that if we denote the pointwise complement of an event
$B$ by $B'$, then $\P(B')=\P(B)$.

Now, if we let $A$ and $B$ be up-events in the uniform hypercube $Q^n$, we have that
$\P(A \Box B) \le \P(A)\P(B)$ by Van den Berg-Kesten while $\P(A \cap B') \le \P(A)\P(B)$
by Harris.  So how do $\P(A \Box B)$ and $\P(A \cap B')$ compare?  In this setting, it seems,
Van den Berg-Kesten is fundamentally stronger than Harris.

Putting it another way, in $A \Box B$ the constituent events are not permitted to
help each another; in $A \cap B'$, they {\em can't} help each other.  Lack of
permission appears to beat incapability as a cause of reduction in probability.

\section{Preliminaries}

If $C \subset Q^n$ and $I \subset \{1,\dots,n\}$, we say that $I$ {\em witnesses}
$x \in C$ if for any $y \in Q^n$, if $y_i = x_i$ for every $i \in I$, then $y \in C$.
When $x$ is chosen randomly from $Q^n$, we say that $A$ and $B$ {\em occur disjointly} if 
there are disjoint sets of indices $I, J$ such that $I$ witnesses $x \in A$ and
$J$ witnesses $x \in B$.  The set of all $x$ with this property is denoted $A \Box B$.

For $x,y \in Q^n$ put $x \le y$ if $x_i \le y_i$ for all $i=1,\dots,n$.  The subset
$A \subset Q^n$ is called an ``up-event'' if $x \le y$ and $x \in A$ implies that $y \in A$.
Down-events are defined similarly.  If $A$ is an up-event, then for any {\em minimal} $I$
witnessing $x \in A$, we have $x_i = 1$ for all $i \in I$; for $x$ in a down-event $D$, 
$x_i=0$ for $i$ in any minimal witness.  It follows that if $A$ is an up-event and $D$
a down-event, then any occurrence of $A \cap D$ is a disjoint occurrence---because
minimal witnesses for each are forced to be disjoint.

We denote the $\{0,1\}$-complement of a point $x$ by $x'$.  If $B$ is an up-event then $B'$ is the down-event
$\{x'|x \in B\}$.  Since point-complementation is an involution and our probability distribution
is uniform, we have $B'' = B$, $|B'|=|B|$ and $\P(B')=\P(B)$.

The coordinate $k$ is said to be {\em pivotal} for $x \in A$ if $x[k] \notin A$,
where $x[k]_i = x_i$ iff $i \not= k$.  A {\em double pivot} for $A$ and $B$ is an
$x$ for which there is a coordinate $k$ that is pivotal relative to $A \Box B$,
and moreover, there are (at least) {\em two} disjoint pairs of witnesses---in one of which
$k$ belongs to the witness for $A$, and in the other $B$.

We assume henceforth that $A$ and $B$ are arbitrary up-events in $Q^n$.
The Van den Berg-Kesten inequality says that $\P(A \Box B) \le \P(A)\P(B)$, and Harris'
inequality assures us that $\P(A \cap B') \le \P(A)\P(B') = \P(A)\P(B)$.  We wish
to compare $\P(A \Box B)$ with $\P(A \cap B')$.

\section{Result}

\begin{theorem}\label{thm:main} Let $A$ and $B$ be up-events in the uniform hypercube $\{0,1\}^n$,
and let $B'$ be the pointwise complement of $B$.  Then $\P(A \Box B) \le \P(A \cap B')$,
with equality if and only if there is no double pivot for $A$ and $B$.
\end{theorem}

\begin{proof}
We prove the non-strict inequality by induction on $n$.  For $x \in Q^{n-1}$ and $\ep \in \{0,1\}$, denote
by $x\ep$ the member of $Q^n$ obtained from $x$ by adding an $n$th coordinate $x_n=\ep$.
For any event $E$, let $E_\ep \subset Q^{n-1}$ be given by $E_\ep := \{x | x\ep \in E\}$;
thus $|E| = |E_0|+|E_1|$.

When $E$ is an up-event, $E_0$ may be thought of as the set of ``short'' strings
that already satisfy $E$, $E_1$ those that will satisfy $E$ if the last coordinate
cooperates.  In particular, $E_0 \subset E_1$.

Let $A$ and $B$ be as in the statement of the theorem; let $C := A \Box B$ and
$D := A \cap B'$.  Then

$$
C_0 = A_0 \Box B_0,
$$
$$
C_1 = (A_0 \Box B_1) \cup (A_1 \Box B_0),
$$
$$
D_0 = A_0 \cap B'_0,~{\rm and}
$$
$$
D_1 = A_1 \cap B'_1~,
$$
where $B'_\ep$ means $(B')_\ep$.

Using our induction hypothesis and the fact that the pointwise complement of $B_\ep$ is $B'_{1-\ep}$, we have
$$
|D| = |D_0| + |D_1| = |A_0 \cap B'_0| + |A_1 \cap B'_1| \ge |A_0 \Box B_1| + |A_1 \Box B_0|~.
$$

But, since $A_0 \Box B_0 \subset (A_0 \Box B_1) \cap (A_1 \Box B_0)$,
$$
|C| = |C_0| + |C_1| = |A_0 \Box B_0| + |(A_0 \Box B_1) \cup (A_1 \Box B_0)|
$$
$$
\le |A_0 \Box B_0| + |A_0 \Box B_1| + |A_1 \Box B_0| - |A_0 \Box B_0| = |A_0 \Box B_1| + |A_1 \Box B_0|~;
$$
comparing the last two displays gives us the desired result.

To characterize the cases of equality, we note that the only case in the induction where equality
is not preserved is when $|(A_0 \Box B_1) \cap (A_1 \Box B_0)| > |A_0 \Box B_0|$, that is,
when $(A_0 \Box B_1) \cap (A_1 \Box B_0))$ contains an $x \notin A_0 \Box B_0$.  Such an $x$,
when padded with zeroes to give it a full $n$ coordinates, is a double pivot for $A$ and $B$. \end{proof}

\section{An example from percolation}

In the proof of Smirnov's theorem (see \cite{S} or, for more detail, \cite{BR}) 
the boundary of a subgraph of the hexagonal lattice is cut into three paths
(with cells labeled 1,2 and 3 as in Fig.~\ref{fig:bbw} below).  A vertex is
chosen in the interior and its neighbor cells labeled $x_1,x_2,x_3$.  Each
interior cell is declared ``open'' independently with probability 1/2, and
closed otherwise.

Let $G_i$ be the event that there is an open path from $x_i$ to a boundary
cell labeled $i$, and $F_i$ the same for a closed path.  The combinatorial
crux of Smirnov's proof is that $\P(F_1 \Box F_2 \Box G_3) = \P(G_1 \Box F_2 \Box G_3)$.
What about $\P(F_1 \Box F_2 \Box G_3)$ versus  $\P(F_1 \Box F_2 \Box F_3)$?  If
we let $A = F_1 \Box F_2$ and $B = F_3$ then the conditions of Theorem~\ref{thm:main}
are satisfied, with ``closed'' corresponding to 1 and ``open'' to 0, and $n=20$.
Thus $\P(F_1 \Box F_2 \Box G_3) \le \P(F_1 \Box F_2 \Box F_3)$. 
The domain pictured in Fig.~\ref{fig:bbw} is the simplest example we were able
to construct in which equality does not hold.

\begin{figure}[ht]
\epsfxsize240pt
$$\epsfbox{bbw.ps}$$
\caption{Critical face percolation on a subgraph of the hexagonal grid.}\label{fig:bbw}
\end{figure}

The difference between the quantities $\P(F_1 \Box F_2 \Box G_3)$ and $\P(F_1 \Box F_2 \Box F_3)$
is pretty small.  A double pivot for $F_1 \Box F_2$ and $F_3$ amounts
to a configuration in which a cell (which could only be $a$ or $c$) can be
used either in a closed path from $x_3$ to the 3-boundary---while a disjoint witness
remains to $F_1 \Box F_2$---or the reverse, but when flipped to ``open'',
ruins $F_1 \Box F_2 \Box F_3$.

There is exacly one such configuration, pictured below in Fig.~\ref{fig:bbw}.
It follows that the difference between
$\P(F_1 \Box F_2 \Box G_3)$ and  $\P(F_1 \Box F_2 \Box F_3)$ is $2^{-20}$.

\begin{figure}[ht]
\epsfxsize240pt
$$\epsfbox{bbb.ps}$$
\caption{The configuration responsible for $\P(F_1 \Box F_2 \Box G_3) > \P(F_1 \Box F_2 \Box F_3)$.}\label{fig:bbb}
\end{figure}

\spacing{1}

\begin{thebibliography}{1}

\bibitem{AD} R. Ahlswede and D. E. Daykin, An inequality for the weights of two families
of sets, their unions and intersections, {\em Z. Wahrsch.\ Verw.\ Gebiete} {\bf 43}, 183--185.

\bibitem{BR} B. Bollob\'{a}s and O. Riordan (2006), {\em Percolation}, Cambridge U. Press,
Cambridge UK.

\bibitem{BF} J. van den Berg and U. Fiebig (1987), On a combinatorial conjecture concerning
disjoint unions of events, {\em Ann.\ Probab.} {\bf 15}, 354--374.

\bibitem{BK} J. van den Berg and H. Kesten (1985), Inequalities with applications to
percolation and reliability, {\em J. Appl.\ Probab.} {\bf 22}, 556--569.

\bibitem{FKG} C. M. Fortuin, P. W. Kasteleyn and J. Ginibre (1971), Correlation inequalities on
some partially ordered sets, {\em Comm.\ Math.\ Phys} {\bf 22}, 89--103.

\bibitem{G} G. Grimmett (1989), {\em Percolation}, 2nd edition, Springer-Verlag, Berlin. 

\bibitem{H} T. E. Harris (1960), A lower bound for the critical probability in a certain percolation
process, {\em Proc.\ Cambridge Philos.\ Soc.} {\bf 56} 13--20.

\bibitem{R} D. Reimer (2000), Proof of the van den Berg-Kesten conjecture, {\em Combin.\
Probab.\ Comput.} {\bf 9}, 27--32.

\bibitem{S} S. Smirnov (2001), Critical percolation in the plane: conformal invariance,
Cardy's formula, scaling limits. {\em C.R. Acad.\ Sci.\ paris S\'{e}r.\ I Math.} {\bf 333}, 239-244.

\end{thebibliography}

\end{document}
