Two-part set systems

Erdős, Péter and Gerbner, Dániel and Lemons, Nathan and Mubayi, D. and Palmer, Cory and Patkós, Balázs (2012) Two-part set systems. ELECTRONIC JOURNAL OF COMBINATORICS, 19. pp. 1-10. ISSN 1077-8926

Preview

Text EGMLPP-EJC12.pdf Download (320kB) | Preview

Abstract

The two part Sperner theorem of Katona and Kleitman states that if X is an n-element set with partition X 1 ∪ X 2, 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 ∩ X i = B ∩ X i 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 X 1, X 2. 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| ≤ 2 n-1 and there are exponentially many examples showing that this bound is tight.

Actions (login required)

Edit Item