EQUALITY IN A RESULT OF KLEITMAN

An upset is a set U of subset of a finite set. S such that if U subset -or-equal-to V and U is-an-element-of U, then V is-an-element-of U. A downset D is defined analogously. In 1966, Kleitman (J. Combin. Theory 1 (1966), 153-155) proved that if U and D are arbitrary up- and downs ets, respectively, then \U\\D\ greater-than-or-equal-to 2\S\ sufficien t condition for equality to hold is: for every minimal element or of U and every maximal element D of D, U subset-or-equalto D. This result is extended to some related inequalities. (C) 1994 Academic Press, Inc .