Difference between revisions
union-closed-sets
Status and infobox
- status:
—→ partial - kind:
—→ problem - year:
—→ 1979 - statement:
—→ In every finite union-closed family of sets, other than the one containing only the empty set, some element belongs to at least half the sets.
Source +22 −0
+---
+title: Union-closed sets conjecture
+kind: problem
+status: partial
+year: 1979
+authors: Péter Frankl
+statement: In every finite union-closed family of sets, other than the one containing only the empty set, some element belongs to at least half the sets.
+space: combinatorics
+---
+For decades nobody could prove any constant fraction. In 2022 Justin Gilmer, then at Google, proved 1%, using an information-theoretic argument. Within weeks others pushed it to about 38%. The last stretch to 50% appears to need a new idea.
+
+Posed 1979, Péter Frankl.
+
+## What would settle it
+
+Lean statement in formal-conjectures
+
+## Sources
+
+- [Wikipedia: Union-closed sets conjecture](https://en.wikipedia.org/wiki/Union-closed_sets_conjecture)
+
+[[Space:combinatorics|Combinatorics]] · [[Continent:mathematics|Mathematics]]
Revision 38 as rendered
For decades nobody could prove any constant fraction. In 2022 Justin Gilmer, then at Google, proved 1%, using an information-theoretic argument. Within weeks others pushed it to about 38%. The last stretch to 50% appears to need a new idea.
Posed 1979, Péter Frankl.
What would settle it
Lean statement in formal-conjectures