Characterizing 3-sets in Union-Closed Families

Abstract

A family of sets is union-closed (UC) if the union of any two sets in the family is also in the family. Frankl's UC sets conjecture states that for any nonempty UC family $\mathcal{F}\subseteq 2^{[n]}$ such that $\mathcal{F}\ne \left\{\varnothing \right\}$, there exists an element $i\in [n]$ that is contained in at least half the sets of $\mathcal{F}$. The 3-sets conjecture of Morris states that the smallest number of distinct 3-sets (whose union is an $n$-set) that ensure Frankl's conjecture is satisfied for any UC family that contains them is $\lfloor n/2\rfloor +1$ for all $n\ge 4$. For an UC family $\mathcal{A}\subseteq 2^{[n]}$, Poonen's Theorem characterizes the existence of weights on $[n]$ which ensure all UC families that contain $\mathcal{A}$ satisfy Frankl's conjecture, however the determination of such weights for specific $\mathcal{A}$ is nontrivial even for small $n$. We classify families of 3-sets on $n\le 9$ using a polyhedral interpretation of Poonen's Theorem and exact rational integer programming. This yields a proof of the 3-sets conjecture.