Skip to content

The Easiest Impossible Problem

May 7, 2014


A simple problem that seems impossible to solve

PeterFranklPins
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 {B_{n}} be the Boolean cube, i.e. the set {\{0,1\}^{n}}. For {x} and {y} in the cube {x \vee y} is {z} where

\displaystyle  z_{i} = x_{i} \vee y_{i}.

Suppose that {f} is a Boolean function defined on {B_{n}} that satisfies for all {x} and {y},

\displaystyle  f(x \vee y) \ge f(x)f(y).

and also {f(0^n) = 0}. Then we will call {f} a Frankl Function (FF).

Let {S(f)} be the number of {x} so that {f(x)=1}. His conjecture is that for any FF there is a coordinate {i} so that

\displaystyle  f(x_{1},\dots,x_{n}) =1

for at least {S(f)/2} values of {x_{1},\dots,x_{n}} values where {x_{i}=1}.

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 {A} and {B} are in the family, then so is {A \cup B}. Then there is a single element {x} 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 {U} of at most {n} elements. We map a set {A} to the obvious vector {A^{*}} so that {i \in A} if and only if {A^{*}_{i}=1}. Then define {f(x)} as the indicator function: {f(x_{1},\dots,x_{n})=1} if and only if the set that {x} represents is in the family. The rule

\displaystyle  f(x \vee y) \ge f(x)f(y)

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 {S(f)} is close to {2^{n}}. I believe the current best result is that {S(f) \ge 2^{n-1}/3}. A natural question is, can this be pushed to {\delta 2^{n}} for any positive {\delta}?

There are results for random {f}. However, these do not prove that the conjecture is true even for most such functions. The conjecture must be weakened to replace {S(f)/2} by {\lambda S(f)} for {\lambda = 1/2 -\epsilon}. There is even a result that proves that the conjecture is true for any Boolean function of at most {12} variables. This is a clever case-analysis proof, but still a case-analysis proof.

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 {f(0^n) = 0} in place of {S(f)>0} as condition on Frankl function; fixed Frankl bio link, put “11” back to 12 variables.]

28 Comments leave one →
  1. May 7, 2014 11:29 am

    I think that for many people this conjecture is what you would call a mathematical disease. But it’s a great problem.

  2. May 7, 2014 11:40 am

    Your link to wikipedia needs an accent in it:
    http://en.wikipedia.org/wiki/P%C3%A9ter_Frankl

  3. Craig permalink
    May 7, 2014 12:46 pm

    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.

    • May 7, 2014 2:13 pm

      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.

      • May 8, 2014 6:00 am

        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…

      • Craig permalink
        May 8, 2014 9:08 am

        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.

      • May 8, 2014 11:15 am

        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.

    • Serge permalink
      June 25, 2014 9:03 am

      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.

  4. May 7, 2014 1:18 pm

    Maybe it should be mentioned that his (joint) birthday conference is in july: http://www.renyi.hu/conferences/summit240/

  5. ChristianB permalink
    May 7, 2014 3:15 pm

    And Ron is a juggler too: http://www.math.ucsd.edu/~fan/ron/

  6. Igor Balla permalink
    May 9, 2014 12:04 pm

    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.

  7. Craig permalink
    May 9, 2014 1:37 pm

    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?

  8. May 11, 2014 7:28 am

    There is a lovely graph theoretic version of the conjecture: http://arxiv.org/abs/1212.4175

Trackbacks

  1. Enriching the Frankl Conjecture | Gödel's Lost Letter and P=NP
  2. Frankl, My Dear : 1 | Inquiry Into Inquiry
  3. Frankl, My Dear : 2 | Inquiry Into Inquiry
  4. Frankl, My Dear : 3 | Inquiry Into Inquiry
  5. Frankl, My Dear : 4 | Inquiry Into Inquiry
  6. Frankl, My Dear : 5 | Inquiry Into Inquiry
  7. Frankl, My Dear : 6 | Inquiry Into Inquiry
  8. Frankl, My Dear : 7 | Inquiry Into Inquiry
  9. Frankl, My Dear : 8 | Inquiry Into Inquiry
  10. Frankl, My Dear : 9 | Inquiry Into Inquiry
  11. Frankl, My Dear : 10 | Inquiry Into Inquiry
  12. Frankl, My Dear : 11 | Inquiry Into Inquiry
  13. Inquiry Into Inquiry
  14. Open Problems That Might Be Easy | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s