New conjectures for union-closed families

Jonad Pulaj¹ ; Annie Raymond² ; Dirk Theis³

¹Zuse Institute Berlin
²University of Washington
³University of Tartu

The electronic journal of combinatorics, Tome 23 (2016) no. 3

Résumé

The Frankl conjecture, also known as the union-closed sets conjecture, states that in any finite non-empty union-closed family, there exists an element in at least half of the sets. From an optimization point of view, one could instead prove that $2a$ is an upper bound to the number of sets in a union-closed family on a ground set of $n$ elements where each element is in at most $a$ sets for all $a,n\in \mathbb{N}^+$. Similarly, one could prove that the minimum number of sets containing the most frequent element in a (non-empty) union-closed family with $m$ sets and $n$ elements is at least $\frac{m}{2}$ for any $m,n\in \mathbb{N}^+$. Formulating these problems as integer programs, we observe that the optimal values we computed do not vary with $n$. We formalize these observations as conjectures, and show that they are not equivalent to the Frankl conjecture while still having wide-reaching implications if proven true. Finally, we prove special cases of the new conjectures and discuss possible approaches to solve them completely.

Détail

DOI : 10.37236/5749

Classification : 05D05, 90C10
Mots-clés : Frankl conjecture, union-closed families, integer programming