The union-closed sets conjecture states that every finite nontrivial union-closed family has an element contained in at least half of its members.
Let be a finite union-closed family whose union is nonempty. Some ground element belongs to at least a proportionof its members. Requiring a nonempty union excludes both the empty set family and , for which no element can be chosen.
Here is the entropy mechanism. Choose independent uniform random members of . Then and , because the union still belongs to . If every element had probability at most of belonging to , Will Sawin's binary entropy estimate would givea contradiction when . A singleton set family with nonempty union satisfies the conclusion directly.[ref]
An improved lower bound for the union-closed sets conjecture by Will Sawin. Theorems1–2 and proof of Theorem1
Articles by others on the same topic
The Union-Closed Sets Conjecture is a problem in combinatorial set theory that deals with the properties of families of sets.