Two-part set systems (Q426823): Difference between revisions
From MaRDI portal
Set profile property. |
Changed an Item |
||
Property / arXiv ID | |||
Property / arXiv ID: 1110.0099 / rank | |||
Normal rank |
Latest revision as of 14:35, 18 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Two-part set systems |
scientific article |
Statements
Two-part set systems (English)
0 references
12 June 2012
0 references
Summary: The two part Sperner theorem of Katona and Kleitman states that if \(X\) is an \(n\)-element set with partition \(X_1 \cup X_2\), and \(\mathcal{F}\) is a family of subsets of \(X\) such that no two sets \(A, B \in \mathcal{F}\) satisfy \(A \subset B (or B \subset A)\) and \(A \cap X_i=B\cap X_i\) for some \(i\), then \(|\mathcal{F}| \leq {n \choose \lfloor n/2\rfloor}\). We consider variations of this problem by replacing the Sperner property with the intersection property and considering families that satisfy various combinations of these properties on one or both parts \(X_1, X_2\). Along the way, we prove the following new result which may be of independent interest: let \(\mathcal{F},\mathcal{G}\) be intersecting families of subsets of an \(n\)-element set that are additionally cross-Sperner, meaning that if \(A \in\mathcal{F}\) and \(B \in \mathcal{G}\), then \(A \not\subset B\) and \(B \not\subset A\). Then \(|\mathcal{F}| +|\mathcal{G}| \leq 2^{n-1}\) and there are exponentially many examples showing that this bound is tight.
0 references
extremal set theory
0 references
sperner
0 references
intersecting
0 references