Characterizing 3-Sets in Union-Closed Families

Abstract

Let $[n]:=\left\{1,2,\dots ,n\right\}$ and let a k-set denote a set of cardinality k. 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 conjecture states that for any nonempty UC family $\mathcal{F}\subseteq 2^{[n]}$ such that $\mathcal{F}\ne \{\varnothing \}$, there exists an element $i\in [n]$ that is contained in at least half the sets of $\mathcal{F}$, where $2^{[n]}$ denotes the power set on $[n]$. 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 (in an element of the n-set) 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.

Keywords:

• Frankl’s conjecture
• 3-sets conjecture
• union-closed families
• integer programming
• extremal combinatorics

Acknowledgments

The author would like to thank Martin Grötschel, Ralf Borndörfer, and Axel Werner for fruitful discussions and helpful comments. Furthermore, the author is indebted to the anonymous reviewers for valuable comments and suggestions that helped improve the exposition of this article.

Declaration of Interest

No potential conflict of interest was reported by the author(s).

Notes

1 Our implementation is freely available at https://github.com/JoniPulaj/cutting-planes-UC-families. Included are examples of the code’s work flow, the actual .lp files used for all verification in this work, and for the interested reader detailed instructions for carrying out an independent verification.

2 The SageMath code is freely available as a Jupiter notebook file and can be downloaded at the following link https://colab.research.google.com/drive/1GFabooPpCkgYESYIVRsxuBtxVYPcxNY3?usp=sharing. The file can be uploaded and viewed on https://cocalc.com/.

3 Runtimes vary from few minutes or less for $n\le 7$ , to less than half an hour for n = 8, and about two hours for $n=9$. Computations were carried out on machines with 2.40 GHz quad-core processors and 16 GB of RAM.

4 We arrive at the isomorphism in entry 4 of Table 6 via $(1,7,9,4,6,2,8,3,5)$ in cycle notation. This is also checked computationally in the aforementioned Jupyter notebook.

5 We arrive at the isomorphism in entry one via (18)(27)(36)(45), and in entry two via (3957)(48). This is also computationally checked in the aforementioned Jupyter notebook.

6 This is also checked computationally in the given Jupyter notebook.

7 Identify with each family a binary matrix where each column represents a set. It suffices to consider the square block structure in the upper left hand corner of the matrices corresponding to $T^{81}and{T}^{82}$. The block structure cannot be recovered in $\mathcal{D}$ by an appropriate choice of $a,b,c,d$. This implies that $\mathcal{D}$ is non-isomorphic to $T^{81}and{T}^{82}$. This is also computationally checked in the given Jupyter notebook.

Additional information

Funding

The work for this article has been (partly) conducted within the Research Campus MODAL funded by the German Federal Ministry of Education and Research (BMBF grant number 05M14ZAM).