The Easiest Impossible Problem
A simple problem that seems impossible to solve
|
|
Article source |
Péter Frankl is a “Hungarian mathematician and street performer”—quoting our friends at Wikipedia. He is also a globetrotter, noting on his personal blog that he has visited over 100 countries. He resides in Japan, where he regularly appears on television to blend mathematics and entertainment for children. He visited Atlanta last July but I did not meet him—he worked with his friend Vojtěch Rödl over at Emory University which is across town. His specialty is extremal combinatorics, which is the study of how large or small a mathematical structure can be and still satisfy certain constraints.
Today I wish to talk about an approach to his famous conjecture.
The amazing thing about the conjecture is that it is so easy to state, yet progress on it seems very difficult. Frankl first stated the conjecture in 1979, and it was publicized quickly by Ron Graham. There is some feeling that the conjecture was known before—it is hard to invent something new. But most call the conjecture the Frankl Conjecture.
The Problem
I will state it as a theory problem. Let 
Suppose that 
and also 
Let 
for at least 
What Is Known
There is a great and relatively recent survey on this conjecture by Henning Bruhn and Oliver Schaudt. It has the cool title “The journey of the union-closed sets conjecture.” The title gives out a secret—the usual statement of the conjecture sounds different from ours. It is:
Consider a finite family of non-empty finite sets. Assume they are closed under union: if
and
are in the family, then so is
. Then there is a single element
that is in at least half of the sets.
Let’s look at why our version is the same.
Theorem: The usual Frankl conjecture is equivalent to our Boolean version.
Let the family lie inside a universe 
just says that the family is closed under union. So our Boolean version is the same.
One type of result is that the conjecture is true provided 
There are results for random 
Open Problems
The reason I like the Boolean function approach is that we have many tools in complexity theory that apply to Boolean functions. The condition that makes a Boolean function a FF one seems to be a pretty natural one. It is a kind of restricted monotone condition. I had hoped to be able to add some thoughtful remarks about the conjecture, but my initial ideas did not work. At least not yet. So I hope that stating the conjecture in this way will lead some of you to make progress.
Can we help attack this conjecture? Fourier methods anyone?
[Corrected 
Trackbacks
- Enriching the Frankl Conjecture | Gödel's Lost Letter and P=NP
- Frankl, My Dear : 1 | Inquiry Into Inquiry
- Frankl, My Dear : 2 | Inquiry Into Inquiry
- Frankl, My Dear : 3 | Inquiry Into Inquiry
- Frankl, My Dear : 4 | Inquiry Into Inquiry
- Frankl, My Dear : 5 | Inquiry Into Inquiry
- Frankl, My Dear : 6 | Inquiry Into Inquiry
- Frankl, My Dear : 7 | Inquiry Into Inquiry
- Frankl, My Dear : 8 | Inquiry Into Inquiry
- Frankl, My Dear : 9 | Inquiry Into Inquiry
- Frankl, My Dear : 10 | Inquiry Into Inquiry
- Frankl, My Dear : 11 | Inquiry Into Inquiry
- Inquiry Into Inquiry
- Open Problems That Might Be Easy | Gödel's Lost Letter and P=NP
I think that for many people this conjecture is what you would call a mathematical disease. But it’s a great problem.
Your link to wikipedia needs an accent in it:
http://en.wikipedia.org/wiki/P%C3%A9ter_Frankl
Probably true for no reason, as Chaitin likes to say. I’m guessing that there is no way to prove it unless you look at every possibility, which would take an infinite amount of time. This is based on my experience trying to solve it. I could be wrong.
However, I wonder if it is possible to come up with a probability-heuristic argument that the conjecture is true.
I think that there are results that are true for no reason, but this one feels like a result that is either true with a very clever proof or false with a fairly large counterexample. My money would be on the former.
At first sight, it looks like another problem whose lack of structure allows one to state it in many different ways. Perhaps the brain, while trying to endow it with some structure, views it more as a phenomenon than as a truth…
The usual Frankl conjecture looks like it is easy to solve at first. When one takes the family of 2^n subsets of {1,2,…,n}, every element is contained in half of the subsets, 2^{n-1} subsets, so one would think that on average any element in the union closure of any subfamily would be in half of its subsets, which would imply the conjecture. But I don’t know how to prove this.
That’s a very natural approach. The problem is that it is hard to make sense of it in a way that isn’t obviously false. For example, if the sets are the empty set, 1, 2, 12 and 123456789, then on average each element is in fewer than half the sets, because all of 3, 4, 5, 6, 7, 8 and 9 are in just one set. One could object to that example on the grounds that the numbers from 3 to 9 are in a sense “equivalent” (the sense being that any set in the collection that contains one of them contains all of them), but there are other examples with a similar flavour where this objection does not apply.
One might then say, “OK, let’s try to prove that there exists a probability measure on the ground set such that on average each element is in half the sets — according to this measure.” Unfortunately, this is trivially equivalent to the original problem, since if x belongs to at least half the sets, then one could take the probability measure that is 1 for every set that contains x and 0 otherwise.
That still doesn’t rule out the approach entirely, however. It is conceivable that there might be a probability measure, defined in a clever way in terms of the set system, such that (i) if you choose a random element according to that probability measure, then on average it belongs to half the sets, and (ii) proving that fact, once you have been told the definition of the probability measure, is reasonably straightforward.
Or maybe true for some very complex reason, requiring hours of computation on a proof assistant like the four-color theorem. There seems to be many simple statements in finite mathematics which have very long proofs. However the union-closed sets conjecture is likely to get proved much before P!=NP, with or without a computer.
Maybe it should be mentioned that his (joint) birthday conference is in july: http://www.renyi.hu/conferences/summit240/
And Ron is a juggler too: http://www.math.ucsd.edu/~fan/ron/
The condition f(0^n) = 0 is not needed, all that is needed is that f is not identically 0. Also, the conjecture is true provided S(f) > 2^{n+1} / 3.
Here’s a related question:
For each n, how many nonisomorphic families of subsets of {1,2,…,n} are there that are closed under union?
There is a lovely graph theoretic version of the conjecture: http://arxiv.org/abs/1212.4175
Thanks for that — I didn’t know about it.