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), 253-264. MR**0457232 (56:15442)****[2]**E. R. Gansner,*On the lattice of order ideals of an up-down poset*(preprint). MR**675856 (84b:06012)****[3]**C. Greene and D. J. Kleitman,*On the structure of Sperner*-*families*, J. Combin. Theory Ser. A**20**(1976), 41-68. MR**0398844 (53:2695)****[4]**-,*Proof techniques in the theory of finite sets*, Studies in Combinatorics (G.-C. Rota, editor), Math. Assoc. Amer., 1978, pp. 22-79. MR**513002 (80a:05006)****[5]**-,*Strong versions of Sperner's theorem*, J. Combin. Theory Ser. A**20**(1976), 80-88. MR**0389608 (52:10439)****[6]**J. R. Griggs,*Symmetric chain orders, Sperner theorems, and loop matchings*, Ph.D. dissertation, Massachusetts Institute of Technology, 1977.**[7]**-,*On chains and Sperner*-*families in ranked posets*, J. Combin. Theory Ser. A**28**(1980), 156-168. MR**563553 (81e:05006)****[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. Combin. Theory**17**(1974), 44-58. MR**0366762 (51:3008)****[10]**W. N. Hsieh and D. J. Kleitman,*Normalized matching in direct products of partial orders*, Stud. Appl. Math.**52**(1973), 285-289. MR**0404064 (53:7870)****[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]**-,*On an extremal property of antichains in partial orders: the LYM property and some of its implications and applications*, Combinatorics (M. Hall and J. H. van Lint, editors), Math. Centre Tracts, Amsterdam, vol. 55, 1974, pp. 77-90. MR**0360379 (50:12829)****[14]**J. Kruskal,*The number of simplices in a complex*, Math. Optimization Techniques, Univ. of California Press, Berkeley and Los Angeles, 1963, pp. 251-278. MR**0154827 (27:4771)****[15]**K.-W. Lih,*Sperner families over a subset*(preprint). MR**583957 (81j:05004)****[16]**D. Lubell,*A short proof of Sperner's theorem*, J. Combin. Theory**1**(1966), 299. MR**0194348 (33:2558)****[17]**R. A. Proctor, M. Saks and D. Sturtevant,*Product partial orders with the Sperner property*(to appear). MR**566433 (81f:06005)****[18]**E. Sperner,*Ein Satz über Untermengen einer endlichen Menge*, Math. Z.**27**(1928), 544-548. MR**1544925****[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