Collections of subsets with the Sperner property

Griggs, Jerrold R.

doi:10.1090/S0002-9947-1982-0637711-2

Collections of subsets with the Sperner property
HTML articles powered by AMS MathViewer

by Jerrold R. Griggs PDF

Trans. Amer. Math. Soc. 269 (1982), 575-591 Request permission

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||Z \cap {X_i}| \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

G. F. Clements, More on the generalized Macaulay theorem. II, Discrete Math. 18 (1977), no. 3, 253–264. MR 457232, DOI 10.1016/0012-365X(77)90129-7
Emden R. Gansner, On the lattice of order ideals of an up-down poset, Discrete Math. 39 (1982), no. 2, 113–122. MR 675856, DOI 10.1016/0012-365X(82)90134-0
Curtis Greene and Daniel J. Kleitman, The structure of Sperner $k$-families, J. Combinatorial Theory Ser. A 20 (1976), no. 1, 41–68. MR 398844, DOI 10.1016/0097-3165(76)90077-7
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
Curtis Greene and Daniel J. Kleitman, Strong versions of Sperner’s theorem, J. Combinatorial Theory Ser. A 20 (1976), no. 1, 80–88. MR 389608, DOI 10.1016/0097-3165(76)90079-0

Symmetric chain orders, Sperner theorems, and loop matchings

Jerrold R. Griggs, On chains and Sperner $k$-families in ranked posets, J. Combin. Theory Ser. A 28 (1980), no. 2, 156–168. MR 563553, DOI 10.1016/0097-3165(80)90082-5

On chains and Sperner

families in ranked posets

L. H. Harper, The morphology of partially ordered sets, J. Combinatorial Theory Ser. A 17 (1974), 44–58. MR 366762, DOI 10.1016/0097-3165(74)90027-2
W. N. Hsieh and D. J. Kleitman, Normalized matching in direct products of partial orders, Studies in Appl. Math. 52 (1973), 285–289. MR 404064, DOI 10.1002/sapm1973523285

A theorem of finite sets

Extremal hypergraph properties

D. J. Kleitman, On an extremal property of antichains in partial orders. The $\textrm {LYM}$ property and some of its implications and applications, Combinatorics (Proc. NATO Advanced Study Inst., Breukelen, 1974) Math. Centre Tracts, No. 56, Math. Centrum, Amsterdam, 1974, pp. 77–90. MR 0360379
Joseph B. Kruskal, The number of simplices in a complex, Mathematical optimization techniques, Univ. California Press, Berkeley, Calif., 1963, pp. 251–278. MR 0154827
Ko Wei Lih, Sperner families over a subset, J. Combin. Theory Ser. A 29 (1980), no. 2, 182–185. MR 583957, DOI 10.1016/0097-3165(80)90007-2
D. Lubell, A short proof of Sperner’s lemma, J. Combinatorial Theory 1 (1966), 299. MR 194348
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, DOI 10.1016/0012-365X(80)90118-1
Emanuel Sperner, Ein Satz über Untermengen einer endlichen Menge, Math. Z. 27 (1928), no. 1, 544–548 (German). MR 1544925, DOI 10.1007/BF01171114