Supersaturation in the Boolean lattice. (English) Zbl 1316.05119
Summary: We seek families of subsets of an \(n\)-set of given size that contain the fewest \(k\)-chains.
We prove a “supersaturation-type” extension of both Sperner’s theorem [E. Sperner, Math. Z. 27, 544–548 (1928; JFM 54.0090.06)] and its generalization by P. Erdős [Bull. Am. Math. Soc. 51, 898–902 (1945; Zbl 0063.01270)]. Erdős [loc. cit.] showed that a largest \(k\)-chain free family in the Boolean lattice is formed by taking all subsets of the \(k-1\) middle sizes. Our result implies that by taking this family together with \(x\) subsets of the \(k\)-th middle size, we obtain a family with the minimum number of \(k\)-chains, over all families of this size. We prove our result using the symmetric chain decomposition method of N. G. de Bruijn et al. [Nieuw Arch. Wiskd., II. Ser. 23, 191–193 (1951; Zbl 0043.04301)].
We prove a “supersaturation-type” extension of both Sperner’s theorem [E. Sperner, Math. Z. 27, 544–548 (1928; JFM 54.0090.06)] and its generalization by P. Erdős [Bull. Am. Math. Soc. 51, 898–902 (1945; Zbl 0063.01270)]. Erdős [loc. cit.] showed that a largest \(k\)-chain free family in the Boolean lattice is formed by taking all subsets of the \(k-1\) middle sizes. Our result implies that by taking this family together with \(x\) subsets of the \(k\)-th middle size, we obtain a family with the minimum number of \(k\)-chains, over all families of this size. We prove our result using the symmetric chain decomposition method of N. G. de Bruijn et al. [Nieuw Arch. Wiskd., II. Ser. 23, 191–193 (1951; Zbl 0043.04301)].
