On the structure of maximum 2-part Sperner families (Q1356670)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the structure of maximum 2-part Sperner families |
scientific article |
Statements
On the structure of maximum 2-part Sperner families (English)
0 references
5 October 1998
0 references
Let \(S_1 \cup S_2\) be a two-coloration of the finite set \(S\). A set system \({\mathcal H} \subset 2^S\) is called 2-part Sperner family iff, for \(E,F \in {\mathcal H}\) and \(E \subset F\), the difference \(F \setminus E\) is not monochromatic. It is easy to see that any Sperner family is a 2-part Sperner family as well. G. O. H. Katona and D. J. Kleitman proved independently that the maximum cardinality of a 2-part Sperner family is the same as of any Sperner family. P. L. Erdős and G. O. H. Katona described the structure of all maximum 2-part Sperner families. This paper gives an elementary proof for this later theorem. It is based on the analysis of symmetric chain decompositions.
0 references
2-part Sperner family
0 references
symmetric chain decomposition
0 references