Saturday, April 12, 2008

This is unsolved. No really,

I recently encountered an amazingly simple unsolved problem known as the Frankl
Conjecture
. Suppose I have a non-empty finite family of finite sets closed under union, is there necessarily an element that is an element in at least half the sets in the family?

For the people who haven't studied set theory in a while here's a quick refresher (everyone else can skip the next three paragraphs). A set is a collection of objects where we do not care about order and things are either in the set or not. So for example {1,2,3} is a set. If something is in a
set we say it is an element of that set. So for example 2 is an element of {1,2,3} but 5 is not an element. Sets are defined just by what elements they have, so for example the set {2,3,5} is the same as the set defined by containing any prime less than 6. Sets also don't just need to contain
integers. You could think about the set of US Presidents or the set of years in which the Yankee's won the pennant. (Some people may note that this actually leads to problems, but I may post on that later).

Now, the union of two sets is the set formed by making the set that contains everything and is generally denoted with a big U. So for example {1,2} U {2,7} = {1,2,7}.

Now the problem is again suppose I have a non-empty finite family of finite sets closed under union, is there necessarily an element that is an element in at least half the sets in the family? First let's think about what families might work. Well, how about {1},{2},{3},{1,2},{2,3},{1,3},{1,2,3} . This is closed under unions (if you are fuzzy on sets this would be good to check). And in fact the conjecture is true, in fact every element appears in exactly half the sets.

Now for everyone: It isn't hard to see that if there are any singletons in the family, that is sets of of the form {a} then one can take your element to be a. And a similar results holds if one has a pair. If there is a set of the form {a,b} then one can show that either a or b appears in at least half the sets. However, this actually breaks down for triplets. There are families closed under union that contain a triplet {a,b,c} and not one of a b or c appears in half the sets.

This problem is fantastically simple to state. It is hard to explain to a non-math person how simple this problem sounds. The fact that it is unsolved is striking. This is one of the things that appeals to me about math. We have problems that can be simply explained to laypeople and yet those problems are unsolved.

2 comments:

Etienne said...

What's wrong with {years the Yankees won or will win the pennant}? Assuming that it is well-defined whether or not the Yankees won in any given year, of course.

Joshua said...

The concern was more general. If one allows general intuitive notions of what constitutes a set issues like Russell's Paradox result.