Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Collections of subsets with the Sperner property

Author: Jerrold R. Griggs
Journal: Trans. Amer. Math. Soc. 269 (1982), 575-591
MSC: Primary 05A05; Secondary 05C35, 06A10, 52A37
MathSciNet review: 637711
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ X = \{ 1, \ldots ,n\} $ and $ Y = \{ 1, \ldots ,k\} $, $ k \leqslant n$. Let $ C(n,\,k)$ be the subsets of $ X$ which intersect $ Y$, ordered by inclusion. Lih showed that $ C(n\,,k)$ has the Sperner property. Here it is shown that $ C(n,\,k)$ has several stronger properties. A nested chain decomposition is constructed for $ C(n,\,k)$ by bracketing. $ C(n,\,k)$ is shown to have the LYM property. A more general class of collections of subsets is studied: Let $ X$ be partitioned into parts $ {X_1}, \ldots ,{X_m}$, let $ {I_1}, \ldots ,{I_m}$ be subsets of $ \{ 0,\,1, \ldots ,\,n\} $, and let $ P = \{ Z \subset X\vert\vert Z \cap {X_i}\vert\, \in {I_i},\,1 \leqslant i \leqslant m\} $. Sufficient conditions on the $ {I_i}$ are given for $ P$ to be LYM, or at least Sperner, and examples are provided in which $ P$ is not Sperner. Other results related to Sperner's theorem, the Kruskal-Katona theorem, and the LYM inequality are presented.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05A05, 05C35, 06A10, 52A37

Retrieve articles in all journals with MSC: 05A05, 05C35, 06A10, 52A37

Additional Information

Article copyright: © Copyright 1982 American Mathematical Society