Combinatorics, Probability and Computing

Proof of the Van den Berg–Kesten Conjecture

a1 Dept. of Mathematics, The College of New Jersey, Ewing, NJ 08628-0718, USA (e-mail:


We prove the following conjecture of J. van den Berg and H. Kesten. For any events [script A] and [script B] in a product probability space, Prob([script A][square][script B]) [less-than-or-eq, slant] Prob([script A])Prob([script B]), where [script A][square][script B] is the event that [script A] and [script B] occur ‘disjointly’.

(Received March 15 1999)
(Revised June 4 1999)