The Easiest Impossible Problem
A simple problem that seems impossible to solve
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.
I will state it as a theory problem. Let be the Boolean cube, i.e. the set . For and in the cube is where
Suppose that is a Boolean function defined on that satisfies for all and ,
and also . Then we will call a Frankl Function (FF).
Let be the number of so that . His conjecture is that for any FF there is a coordinate so that
for at least values of values where .
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 of at most elements. We map a set to the obvious vector so that if and only if . Then define as the indicator function: if and only if the set that represents is in the family. The rule
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 is close to . I believe the current best result is that . A natural question is, can this be pushed to for any positive ?
There are results for random . However, these do not prove that the conjecture is true even for most such functions. The conjecture must be weakened to replace by for . There is even a result that proves that the conjecture is true for any Boolean function of at most variables. This is a clever case-analysis proof, but still a case-analysis proof.
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 in place of as condition on Frankl function; fixed Frankl bio link, put “11” back to 12 variables.]