Remote Access Transactions of the American Mathematical Society
Green Open Access

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
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 $ 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?)

  • [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 $ k$-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 $ k$-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 $ k$-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.

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: https://doi.org/10.1090/S0002-9947-1982-0637711-2
Article copyright: © Copyright 1982 American Mathematical Society

American Mathematical Society