Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
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

PII: S 0002-9947(1982)0637711-2
Article copyright: © Copyright 1982 American Mathematical Society

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia