Functional van den Berg-Kesten-Reimer Inequalities and their Duals, with Applications

The BKR inequality conjectured by van den Berg and Kesten in [11], and proved by Reimer in [8], states that for $A$ and $B$ events on $S$, a finite product of finite sets $S_i,i=1,\dots ,n$, and $P$ any product measure on $S$, $$P(A\mathrm{\square }B)\le P(A)P(B),$$ where the set $A\mathrm{\square }B$ consists of the elementary events which lie in both $A$ and $B$ for `disjoint reasons.’ Precisely, with $\mathbf{n}:=\{1,\dots ,n\}$ and $K\subset \mathbf{n}$, for $\mathbf{x}\in S$ letting $[\mathbf{x}{]}_K=\{\mathbf{y}\in S:y_i=x_i,i\in K\}$, the set $A\mathrm{\square }B$ consists of all $\mathbf{x}\in S$ for which there exist disjoint subsets $K$ and $L$ of $\mathbf{n}$ for which $[\mathbf{x}{]}_K\subset A$ and $[\mathbf{x}{]}_L\subset B$. The BKR inequality is extended to the following functional version on a general finite product measure space $(S,\mathbb{S})$ with product probability measure $P$, $$E\{\underset{}{\max }{\underset{‾}{f}}_K(\mathbf{X}){\underset{‾}{g}}_L(\mathbf{X})\}\le E\{f(\mathbf{X})\}E\{g(\mathbf{X})\},$$ where $f$ and $g$ are non-negative measurable functions, ${\underset{‾}{f}}_K(\mathbf{x})=\mathrm{e}\mathrm{s}\mathrm{s}{\inf }_{\mathbf{y}\in [\mathbf{x}{]}_K}f(\mathbf{y})$ and $\underline{g}L({\bf x}) = {\rm ess} \inf{{\bf y} \in [{\bf x}]_L}g({\bf y}).$TheoriginalBKRinequalityisrecoveredbytaking$f({\bf x})={\bf 1}A({\bf x})$and$g({\bf x})={\bf 1}B({\bf x})$, and applying the fact that in general ${\bf 1}{A \Box B} \le \max{K \cap L = \emptyset} \underline{f}_K({\bf x}) \underline{g}_L({\bf x})$. Related formulations, and functional versions of the dual inequality on events by Kahn, Saks, and Smyth [6], are also considered. Applications include order statistics, assignment problems, and paths in random graphs.