Two-part set systems

Péter L. Erdős ; Dániel Gerbner ; Nathan Lemons ; Dhruv Mubayi ; Cory Palmer ; Balázs Patkós

The electronic journal of combinatorics, Tome 19 (2012) no. 1

Résumé

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}| \le {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}| \le 2^{n-1}$ and there are exponentially many examples showing that this bound is tight.

Détail

DOI : 10.37236/2067

Classification : 05D05
Mots-clés : extremal set theory, sperner, intersecting