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

DOI:
https://doi.org/10.1090/S0002-9947-1982-0637711-2

MathSciNet review:
637711

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let and , . Let be the subsets of which intersect , ordered by inclusion. Lih showed that has the Sperner property. Here it is shown that has several stronger properties. A nested chain decomposition is constructed for by bracketing. is shown to have the LYM property. A more general class of collections of subsets is studied: Let be partitioned into parts , let be subsets of , and let . Sufficient conditions on the are given for to be LYM, or at least Sperner, and examples are provided in which is not Sperner. Other results related to Sperner's theorem, the Kruskal-Katona theorem, and the LYM inequality are presented.

**[1]**G. F. Clements,*More on the generalized Macaulay theorem. II*, Discrete Math.**18**(1977), no. 3, 253–264. MR**0457232**, https://doi.org/10.1016/0012-365X(77)90129-7**[2]**Emden R. Gansner,*On the lattice of order ideals of an up-down poset*, Discrete Math.**39**(1982), no. 2, 113–122. MR**675856**, https://doi.org/10.1016/0012-365X(82)90134-0**[3]**Curtis Greene and Daniel J. Kleitman,*The structure of Sperner 𝑘-families*, J. Combinatorial Theory Ser. A**20**(1976), no. 1, 41–68. MR**0398844****[4]**Curtis Greene and Daniel J. Kleitman,*Proof techniques in the theory of finite sets*, Studies in combinatorics, MAA Stud. Math., vol. 17, Math. Assoc. America, Washington, D.C., 1978, pp. 22–79. MR**513002****[5]**Curtis Greene and Daniel J. Kleitman,*Strong versions of Sperner’s theorem*, J. Combinatorial Theory Ser. A**20**(1976), no. 1, 80–88. MR**0389608****[6]**J. R. Griggs,*Symmetric chain orders, Sperner theorems, and loop matchings*, Ph.D. dissertation, Massachusetts Institute of Technology, 1977.**[7]**Jerrold R. Griggs,*On chains and Sperner 𝑘-families in ranked posets*, J. Combin. Theory Ser. A**28**(1980), no. 2, 156–168. MR**563553**, https://doi.org/10.1016/0097-3165(80)90082-5**[8]**J. R. Griggs, M. Saks and D. Sturtevant,*On chains and Sperner*-*families in ranked posets*. II (to appear).**[9]**L. H. Harper,*The morphology of partially ordered sets*, J. Combinatorial Theory Ser. A**17**(1974), 44–58. MR**0366762****[10]**W. N. Hsieh and D. J. Kleitman,*Normalized matching in direct products of partial orders*, Studies in Appl. Math.**52**(1973), 285–289. MR**0404064****[11]**G. O. H. Katona,*A theorem of finite sets*, Proc. Tihany Conf., 1966, Budapest, 1968.**[12]**D. J. Kleitman,*Extremal hypergraph properties*, Surveys in Combinatorics, Proc. 7th British Comb. Conf. (B. Bollobás, editor), London Math. Soc. Lecture Note Series no. 38, 1979.**[13]**D. J. Kleitman,*On an extremal property of antichains in partial orders. The 𝐿𝑌𝑀 property and some of its implications and applications*, Combinatorics (Proc. NATO Advanced Study Inst., Breukelen, 1974) Math. Centrum, Amsterdam, 1974, pp. 77–90. Math. Centre Tracts, No. 56. MR**0360379****[14]**Joseph B. Kruskal,*The number of simplices in a complex*, Mathematical optimization techniques, Univ. of California Press, Berkeley, Calif., 1963, pp. 251–278. MR**0154827****[15]**Ko Wei Lih,*Sperner families over a subset*, J. Combin. Theory Ser. A**29**(1980), no. 2, 182–185. MR**583957**, https://doi.org/10.1016/0097-3165(80)90007-2**[16]**D. Lubell,*A short proof of Sperner’s lemma*, J. Combinatorial Theory**1**(1966), 299. MR**0194348****[17]**Robert A. Proctor, Michael E. Saks, and Dean G. Sturtevant,*Product partial orders with the Sperner property*, Discrete Math.**30**(1980), no. 2, 173–180. MR**566433**, https://doi.org/10.1016/0012-365X(80)90118-1**[18]**Emanuel Sperner,*Ein Satz über Untermengen einer endlichen Menge*, Math. Z.**27**(1928), no. 1, 544–548 (German). MR**1544925**, https://doi.org/10.1007/BF01171114**[19]**A. Wareham, Ph.D. dissertation, University of California, Riverside, 1980.

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:
https://doi.org/10.1090/S0002-9947-1982-0637711-2

Article copyright:
© Copyright 1982
American Mathematical Society