Two-part set systems

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

Research output: Contribution to journalArticlepeer-review

Abstract

The two part Sperner theorem of Katona and Kleitman states that if X is an n-element set with partition X1 ∪ X2, and F is a family of subsets of X such that no two sets(A, B)∈ F satisfy A ⊂ B (or B ε A) and A ∩ Xi = B ∩ Xi for some i, then F ≤ n. We consider variations of this problem by replacing the Sperner ⌊n/2⌋ property with the intersection property and considering families that satisfy various combinations of these properties on one or both parts X1, X2. Along the way, we prove the following new result which may be of independent interest: let F, G be intersecting families of subsets of an n-element set that are additionally cross-Sperner, meaning that if A ∈ F and B ∈ G, then A ⊂ B and B ⊂ A. Then |F| + |G| ≤ 2n-1 and there are exponentially many examples showing that this bound is tight.

Original languageEnglish
Pages (from-to)1-10
Number of pages10
JournalElectronic Journal of Combinatorics
Volume19
DOIs
StatePublished - 2012

Keywords

  • Extremal set theory
  • Intersecting
  • Sperner

Fingerprint

Dive into the research topics of 'Two-part set systems'. Together they form a unique fingerprint.

Cite this