On cross-intersecting families of set partitions

Abstract

Let B(n) denote the collection of all set partitions of [n]. Suppose A1, A2 ⊆ B(n) are cross-intersecting i.e. for all A1 ∈ A1 and A2 ∈ A2, we have A1 ∩ A2 ≠ {circled division slash}. It is proved that for sufficiently large n, |A1| |A2| ≤ B2 n-1 where Bn is the n-th Bell number. Moreover, equality holds if and only if A1 = A2 and A1 consists of all set partitions with a fixed singleton.