Mathematical Sciences Department Discrete Mathematics Seminar: Sam Adriaensen, WPI

Title: Recent progress on the union-closed sets conjecture.

Abstract: The union-closed sets conjecture is an innocent-looking conjecture, that has withstood decades of efforts to prove it. A family of F of sets is called union-closed if for any two members of F, their union is also in F. The infamous conjecture states the if F is a union-closed family of finite sets containing a non-empty set, then there must be an element which is contained in at least half of the members of F.

In this talk, I will not discuss my own research, but instead highlight 2 recent breakthroughs towards proving the conjecture.

The first one states that it holds for large families. More specifically, Karpas proved in 2017 that if F consists of at least half of the subsets of some finite set, then the conjecture holds. He employed techniques from Boolean analysis.

The second one, which is even more impressive, occurred about 2 years ago. Gilmer used entropy (in the sense of Shannon) to prove that ifF is union-closed, some element occurs in at least 1% of its elements. His arguments were optimized and pushed to about 38% independently by many sets of authors.

In my opinion, both results use beautiful ideas, which are not that hard to unpack, and are worth taking the time to appreciate.