Skip to main content
5 of 5
Names of references
LSpice
  • 12.9k
  • 4
  • 45
  • 69

One from just a few days ago is Justin Gilmer's breakthrough on the union-closed conjecture, also known as Frankel's conjecture, which says that if one has a finite family of sets which are closed under taking unions, then at least one element appears in at least half the sets. This seems like a really basic combinatorics question and you can see how easily it generates interest by among other things how many Mathoverflow questions there have been about it. It seems like one of those problems where once you hear about it, you have to resist the temptation to just drop things and try to find a simple proof.

But a lot of the obvious things one would try to do for this question fail. We'll say an element is abundant if it appears in at least half of the sets in the family. It isn't too hard to show that if one of your sets is a singleton $\{x\}$ then $x$ must be abundant. And if the smallest size set in your family is two elements, then at least one of its elements in abundant. But the obvious generalization is false. It is possible for none of the abundant elements to appear in the smallest size sets in your family. See discussion at Difficult examples for Frankl's union-closed conjecture.

And there are other things that one might hope for that can break down. For example, the set of elements which appear in at least half the elements need not be itself in our family (see A strengthening of Frankl's union-closed conjecture?).

The strongest results until a few days could not even construct an explicit constant $\delta >0$ where we could prove the weaker union closed conjecture with $\delta$ replacing $\frac{1}{2}$. However,[Justin Gilmer gave a very readable proof at A constant lower bound for the union-closed sets conjecture that such a collection has to have an element which appears in at least 1/100th of all the members in the collection. For more details, see Gil Kalai's discussion at Amazing: Justin Gilmer gave a constant lower bound for the union-closed sets conjecture.

The natural limit to the method of Gilmer is $\frac{3- \sqrt{5}}{2} \approx 0.38$ rather than $\frac{1}{2}$, and there was some speculation that getting up there might be a slog, and some people thought that this might not be a bad idea for a new Polymath project (in a vein similar to the one on prime gaps). However, nearly simultaneously, three different preprints getting the $\frac{3- \sqrt{5}}{2}$ bound appeared, all using slightly different methods (one, An improved lower bound for the union-closed set conjecture, by @WillSawin; two, Approximate union closed conjecture, by a pair of stack exchange users in Mathematics and Theoretical Computer Science, Zachary Chase and Shachar Lovett; and three Improved Lower Bound for Frankl's Union-Closed Sets Conjecture, by @RyanAlweiss, Brice Huang, and Mark Sellke). One of them actually has potential to move beyond that bound.

To some extent the union-closed conjecture is a good example of how there are some really basic things we still don't know. This breakthrough helps alleviate some of that. And it looks plausible that aspects of Gilmer's method may work on some other problems also.

JoshuaZ
  • 7k
  • 2
  • 27
  • 59