The inequality conjectured by van den Berg and Kesten in [9], and proved by Reimer in [6], states that for A and B events on S, a product of finitely many finite sets, and P any product measure on S,P(AÊB) <FONT FACE="Symbol">£</FONT> P(A)P(B), where AÊB are the elementary events which lie in both A and B for `disjoint reasons.' This inequality on events is the special case, for indicator functions, of the inequality having the following formulation. Let X be a random vector with n independent components, each in some space Si (such as R<SUP>d</SUP>), and set S = <FONT FACE="Symbol">Õ</FONT> Si. Say that the function f : S <FONT FACE="Symbol">®</FONT> R depends on K <FONT FACE="Symbol">Í</FONT> {1,...,n} if f(x) = f(y) whenever x<SUB>i</SUB> = y<SUB>i</SUB> for all i <FONT FACE="Symbol">Î</FONT> K. Then for any given finite or countable collections of non-negative real valued functions {f<SUB><FONT FACE="Symbol">a</FONT></SUB>}<SUB><FONT FACE="Symbol">a</FONT><FONT FACE="Symbol">Î</FONT>A</SUB>, {g<SUB><FONT FACE="Symbol">b</FONT></SUB>}<SUB><FONT FACE="Symbol">b</FONT><FONT FACE="Symbol">Î</FONT>B</SUB> on S which depend on K<SUB><FONT FACE="Symbol">a</FONT></SUB> and L<SUB><FONT FACE="Symbol">b</FONT></SUB> respectively, E{sup<SUB>K<SUB><FONT FACE="Symbol">a</FONT></SUB><FONT FACE="Symbol">Ç</FONT>L<SUB><FONT FACE="Symbol">b</FONT></SUB></SUB> f<SUB><FONT FACE="Symbol">a</FONT></SUB>(X) g<SUB><FONT FACE="Symbol">b</FONT></SUB>(X)} <FONT FACE="Symbol">£</FONT> E{sup f<SUB><FONT FACE="Symbol">a</FONT></SUB>(X)} E{sup g<SUB><FONT FACE="Symbol">b</FONT></SUB>(X)}. Related formulations, and functional versions of the dual inequality on events by Kahn, Saks, and Smyth [4], are also considered. Applications include order statistics, assignment problems, and paths in random graphs.
