Conjectures
Union-Closed Sets Conjecture
YOON-yun-klohzd sets kon-JEK-cher
Also Known As Frankl's Conjecture
Combinatorics
Citation Formats
General Reference
APA Style
BibTeX
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.
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 Cross-Tradition Connections
Sources
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 open reader challenges)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.
View At A Past Year
The atlas records no dated fact of its own for this entry, so there is no other year to choose.