Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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

DOI: http://dx.doi.org/10.1090/S0002-9947-1982-0637711-2
PII: S 0002-9947(1982)0637711-2
Article copyright: © Copyright 1982 American Mathematical Society