Flattening antichains with respect to the volume. (English) Zbl 0913.05092

Electron. J. Comb. 6, No. 1, Research paper R1, 12 p. (1999); printed version J. Comb. 6, 1-12 (1999).
Given a (finite) poset \((P,\leq)\) with a strictly increasing function \(h:P\to N=\{0,1,2, \dots\}\), define the volume of a subset \(S\) of \(P\) (with respect to \(h\)) to be \(\sum_{x\in S} h(x)\). A subset \(S\) of \(P\) is flat (with respect to \(h)\) if \(x,y\in S\) with \(h(x)<h(y)\) implies there is no \(z\in P\) such that \(h(x)< h(z)<h(y)\). Thus, if \(P=B_n\), the lattice of subsets of \([n]=\{1, \dots, n\}\), and \(h(x)= | x|\), then \(S\) is flat if there exists a \(k\) such that every element of \(S\) has cardinality \(k\) or \(k+1\). There are many posets which are themselves flat with respect to some function \(h\). Many more (e.g., chains) have flat antichains only. It has been conjectured that \(B_n\) is among the posets which have the property that for every antichain there is a flat antichain with the same volume \((h(x)= | x|)\). Special cases occur in the literature. In this paper the conjecture is settled positively via a sequence of quite elegant technical lemmas based on results by Sperner, Clements and Daykin, among others. Rather than closing a area of inquiry it may also be the case that this paper can be adapted to a more general situation and lead to other interesting conjectures.


05D99 Extremal combinatorics
06A07 Combinatorics of partially ordered sets
06E99 Boolean algebras (Boolean rings)


poset; volume; flat; antichain
Full Text: EuDML EMIS