Union-Closed Buckets

Buckets-3-colorIn the mines of mathematical conundrums there are a few gems that shine brightly.   Such problems are illuminated with the delight of recreational enjoyment.    Whether it be folding unique shapes with paper or exploring the elementary nature of prime numbers, these problems draw a general audience into the awe of patterns and relationships.  Over the years, many communicators of these gems have looked for ways to make them shine even brighter.

The greatest communicator of mathematical conundrums in modern history was Martin Gardner.  Gardner wrote the monthly Mathematical Games column for Scientific American from 1956 to 1981. His first article was on a unique way to fold paper and its properties entitled “Hexaflexagons”.   In the same vein with his original article, Gardner uniquely picked the right gems and polished them to shine the brightest before being displayed.  Following his example, I would like to recast a series of abstract problems into problems of a more recreational nature. To start the series off, I have chosen an unsolved problem in Set Theory known as the Union-Closed Sets Conjecture proposed by Péter Frankl in 1979.

Imagine a shelf with finitely many buckets on it.   Each bucket is either empty or contains at least one colored ball (let most of the buckets have more than one) with the condition that the buckets cannot all be empty.   Furthermore,  let it be true that I can take any two buckets off  the shelf and empty their contents into one bucket not on the shelf (call it bucket B) such that bucket B, with its new contents, is identical to some bucket on the shelf.   Thus, do at least half of the buckets on the shelf share a ball of the same color?

The formal generalized statement of the conjecture is the following:

Union-Closed Sets Conjecture: (Péter Frankl , 1979)  If  the union of any two sets in a finite family of finite sets belongs to the family, then there exists an element of the sets that exists in at least half of the sets.

There are several known results which can easily be found by a quick search.  For instance, Ian Roberts and Jamie Simpson in their paper “A note on the union-closed sets conjecture” in 2010 proved that the conjecture is true for families with at most 46 sets (or 46 buckets to keep with the recreational statement of the conjecture).

However, the general case is still very much unsolved.  It is not clear on where a solution of such a problem can come from.  Sometimes it can come from readers like you.   Can you provide a solution?

About Avery Carr

Avery Carr is a senior analyst and past senior editor for the American Mathematical Society Grad Blog. He and his wife, Alison, live in Olive Branch, MS.
This entry was posted in General, Math, Math Games, Uncategorized. Bookmark the permalink.