Progress on the union-closed sets conjecture

The union-closed sets conjecture is the following extremely easy to state conjecture about subsets of finite sets: Assume that \(\mathcal{F}\) is a family of subsets of \(\{1, 2, \ldots, n\}\) which is union-closed; this means that for any two sets \(A,B\) in \(\mathcal{F}\) their union \(A \cup B\) is also a member of \(\mathcal{F}\). Then there exists an element \(k \in \{1, 2, \ldots, n\}\) which belongs to at least half of the members of \(\mathcal{F}\).

In a recent preprint (only 9 pages long!) J. Gilmer now gave the first constant lower bound; concretely, he proved that there is an element \(k \in \{1, 2, \ldots, n\}\) which belongs to at least a \(0.01\) fraction of the sets in \(\mathcal{F}\).

Only a few days later three other preprints (here, here, and here) were independently put on the arXiv improving Gilmer’s lower bound to \((3-\sqrt{5})/2 \cong 0.38\). Note that the conjecture postulates the lower bound of \(0.5\).

I learned about this major progress from the blog of Gil Kalai (here).

edit (Nov 30th): See also this follow-up post by Gil Kalai: link. Also, there are now five (and not three as written above) preprints extending Gilmer’s arguments.

Leave a Reply

Your email address will not be published.