Alexander Razborov, Nikolay Vereshchagin

Assume that A, B are finite families of n-element sets.

We prove that there is an element that simultaneously

belongs to at least |A|/2n sets

in A and to at least |B|/2n sets in B. We use this result to prove

that for any inconsistent DNF's F,G with OR ...
more >>>