Supersaturation in the Boolean lattice
Supersaturation in the Boolean lattice
复制标题
布尔晶格中的过饱和
作者：
A. P. Dove;Jerrold R. Griggs;Ross J. Kang;Jean
我们证明了 Sperner 定理 (1928) 的“过饱和型”扩展以及 Erdos (1945) 对 k 链的推广。我们的结果意味着，最大族的大小比最大 k 链自由族的大小大 x 且包含最小数量的 k 链，该族是通过取布尔晶格的中间 (k-1) 行和第 k 个中间行中的 x 个元素而形成的族。我们证明了使用 de Bruijn、van Ebbenhorst Tengbergen 和 Kruyswijk (1951) 的对称链分解方法得出的结果。
We prove a "supersaturation-type'' extension of both Sperner's Theorem (1928) and its generalization by Erdos (1945) to k-chains. Our result implies that a largest family whose size is x more than the size of a largest k-chain free family and that contains the minimum number of k-chains is the family formed by taking the middle (k-1) rows of the Boolean lattice and x elements from the k-th middle row. We prove our result using the symmetric chain decomposition method of de Bruijn, van Ebbenhorst Tengbergen, and Kruyswijk (1951).