Consider two set systems A and B in the powerset P(n) with the property that for each A # A there exists a unique B # B such that A/B. Ahlswede and Cai proved an inequality about such systems which is a generalization of the LYM and Bolloba s inequalities. In this paper we characterize the structure of the extremal cases.
1996 Academic Press, Inc.
NOTATION
We are concerned with the poset P(n)=P ([1, 2, ..., n]). This is the power set of [n]=[1, 2, ..., n], ordered by inclusion. A set system is simply a subset of P(n). A set system is an antichain if no two of its members are comparable. Conversely a chain is a totally ordered set system. We shall often consider maximal chains; those chains which cannot be extended. In particular such chains contain exactly one set from each of the levels of P(n). The kth level is the system [n] (k) =[A # P(n) : |A| =k]. There are exactly n! maximal chains in P(n).
Occasionally we think of P(n) as a graph with edges AB for all A, B # P(n) with |A2B| =1.
An upset is a set system U with the property that A#B # U implies A # U. A downset is defined similarly. If A is an arbitrary set system we use U (A) to denote the upset generated by A; i.e., U (A)= [X # P(n) : _A # A, A/X]. The downset generated by A, denoted D(A), is defined similarly.