Collections of subsets with the Sperner property
Author:
Jerrold R. Griggs
Journal:
Trans. Amer. Math. Soc. 269 (1982), 575591
MSC:
Primary 05A05; Secondary 05C35, 06A10, 52A37
MathSciNet review:
637711
Fulltext PDF Free Access
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 KruskalKatona 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
(56 #15442)
 [2]
Emden
R. Gansner, On the lattice of order ideals of an updown
poset, Discrete Math. 39 (1982), no. 2,
113–122. MR
675856 (84b:06012), http://dx.doi.org/10.1016/0012365X(82)901340
 [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 (53 #2695)
 [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
(80a:05006)
 [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 (52 #10439)
 [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
(81e:05006), http://dx.doi.org/10.1016/00973165(80)900825
 [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
(51 #3008)
 [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
(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]
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
(50 #12829)
 [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
(27 #4771)
 [15]
Ko
Wei Lih, Sperner families over a subset, J. Combin. Theory
Ser. A 29 (1980), no. 2, 182–185. MR 583957
(81j:05004), http://dx.doi.org/10.1016/00973165(80)900072
 [16]
D.
Lubell, A short proof of Sperner’s lemma, J.
Combinatorial Theory 1 (1966), 299. MR 0194348
(33 #2558)
 [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 (81f:06005), http://dx.doi.org/10.1016/0012365X(80)901181
 [18]
Emanuel
Sperner, Ein Satz über Untermengen einer endlichen Menge,
Math. Z. 27 (1928), no. 1, 544–548 (German). MR
1544925, http://dx.doi.org/10.1007/BF01171114
 [19]
A. Wareham, Ph.D. dissertation, University of California, Riverside, 1980.
 [1]
 G. F. Clements, More on the generalized Macaulay theorem. II, Discrete Math. 18 (1977), 253264. MR 0457232 (56:15442)
 [2]
 E. R. Gansner, On the lattice of order ideals of an updown 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), 4168. 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. 2279. MR 513002 (80a:05006)
 [5]
 , Strong versions of Sperner's theorem, J. Combin. Theory Ser. A 20 (1976), 8088. 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), 156168. 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), 4458. 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), 285289. 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. 7790. 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. 251278. 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), 544548. MR 1544925
 [19]
 A. Wareham, Ph.D. dissertation, University of California, Riverside, 1980.
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/S00029947198206377112
PII:
S 00029947(1982)06377112
Article copyright:
© Copyright 1982
American Mathematical Society
