New conjectures for union-closed families (Q311524): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q257226 |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 00:58, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | New conjectures for union-closed families |
scientific article |
Statements
New conjectures for union-closed families (English)
0 references
13 September 2016
0 references
Summary: 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.
0 references
Frankl conjecture
0 references
union-closed families
0 references
integer programming
0 references