The union-closed sets conjecture, also called Frankl's conjecture, states that in every finite union-closed family of sets, other than the family containing only the empty set, some element belongs to at least half the sets in the family. A family of sets is union-closed if the union of any two sets in it is also in the family. Peter Frankl proposed the conjecture in 1979 in terms of intersection-closed families; the union-closed version was first published by Duffus in 1985. The conjecture is proven for small cases (families of at most 50 sets, or whose union has at most 12 elements) but remains open in general. A 2022 breakthrough by Justin Gilmer gave the first constant-fraction partial result, later refined to show that some element belongs to at least 38.1966 percent of the sets, well short of the conjectured 50 percent. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
StatementFor every finite union-closed family of sets, other than the family containing only the empty set, there exists an element that belongs to at least half of the sets in the family. 1 Proposed Year Prize StatusNot a Millennium Prize Problem; no major institutional cash prize is attached to its proof. 1 Progress Toward ResolutionProven for families of at most 50 sets, for families whose union has at most 12 elements, and for families whose smallest set has one or two elements. In 2022 Justin Gilmer showed that every union-closed family (other than the family containing only the empty set) has an element belonging to at least 0.38271 of its sets, later refined toward about 0.381966; this improved on Gilmer's own initial bound of 0.01. Timothy Gowers has called it one of the best known open problems in combinatorics. 1 Classification
Resolution Status Prize Status
Prize Status (category) Connections
In Branch
Source Union-Closed Sets Conjecture (Wikipedia)
Open Questions
Source Union-Closed Sets Conjecture (Wikipedia)
Posed By
Source Union-Closed Sets Conjecture (Wikipedia)
Sources
1. Union-Closed Sets Conjecture (Wikipedia)
Wikipedialead section
For every finite union-closed family of sets, other than the empty family, there exists an element that belongs to at least half of the sets in the family.
History section
Peter Frankl stated the conjecture in terms of intersection-closed set families in 1979, and so the conjecture is usually credited to him.
Partial results section
one of the best known open problems in combinatorics
In Branch: Combinatorics, Opening paragraph
an open problem in combinatorics posed by Peter Frankl in 1979
View the Source Open Questions (1 open question)
Does every finite union-closed family of sets, other than the family holding only the empty set, really contain an element belonging to at least half of the sets in the family?
The conjecture is confirmed for families of at most 50 sets and other special cases, and Gilmer's 2022 argument reaches only a weaker constant near 0.38 rather than 0.5, so no proof reaches the full one-half bound for every family.
What would resolve this A proof that some element always belongs to at least half of the sets in any union-closed family, or a counterexample family where no element does.
CombinatoricsUnion-Closed Sets Conjecture (Wikipedia)
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.