Skip to content

Enriching the Frankl Conjecture

September 2, 2014


See a number, make a set

BruhnSchaudt

Henning Bruhn and Oliver Schaudt are mathematicians or computer scientists, or both. They are currently working in Germany, but wrote their survey on the Frankl Conjecture (FC) while working together in Paris. Schaudt is also known as an inventor of successful mathematical games.

Today Ken and I wish to talk about the Frankl conjecture and a principle of mathematics.

Before we start let’s be up-front: The FC is a mathematical disease. Ken and I are trying to avoid catching a full blown case—well Ken also has a lot on his plate in the chess world. We have some small insights to share—perhaps doing this will help someone solve the problem, or at least advance the understanding of it. In any case talking about it may keep us from being completely infected.

We covered the conjecture last spring. As Bruhn and Schaudt’s survey relates, FC probably pre-dates Péter Frankl’s 1979 formulation of it while he was in-transit from Paris to Montreal, but all agree that Frankl was the last to discover it. It reads:

If a family {\cal F} of subsets of a finite set {U} is closed under union, then there is an element of {U} that belongs to at least half of the sets in the family.

One may suppose that the {\emptyset} always belongs to the union-closed family. The “half” is tight, as follows on considering the power set of {U} as the family.

The Survey

The survey covers several equivalent forms of the FC, but not the simple re-statement involving the following “Frankl Property” (FP) for Boolean functions {f} on {\{0,1\}^n}:

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

The Frankl Conjecture (FC) property then reads: there is an {i} such that at least half of the satisfying assignments {x} have {x_i = 1}. The conjecture itself then states:

If {f} has FP, then it satisfies FC.

The survey actually emphasizes the dual form, which in our terms involves the function {f'(x) = f(x')}, where {x'} is the bit-flip of {x}. FP becomes {f'(u \wedge v) \geq f'(u)f'(v)}, which means that the satisfying assignments of the flipped function correspond to an intersection-closed family of sets. The FC then states that there is an {i} such that at most half the satisfying assignments {u} of {f'} have {u_i = 1}. Just to be different, we stay with the union-closed form, though in fact Frankl stated the other. Then the survey’s equivalent statements include:

  • Every finite lattice {S} has an element that is not a greatest lower bound of two other elements, but sits above at most half the elements (including itself).

  • Every non-trivial graph has a “popular edge,” meaning an edge both of whose vertices belong to at least half of the minimal vertex covers.

We say more about lattices below–the nifty fact is that the Frankl Property makes the satisfying assignments (plus {0^n}) into a lattice. The graph statement actually comes from a paper by Bruhn and Schaudt with Pierre Charbit and Jan Arne Telle, the last of whom hosted Ken for lectures in Bergen, Norway, two years ago. Since every vertex cover must include at least one vertex from every edge, at least one vertex from every edge must belong to half or more of the minimal covers. Extending this reasoning shows that every odd cycle has a popular edge, so the statement is problematic only for bipartite graphs.

The survey authors say the lattice statement strips FC “down to its bare essential parts: the elements have vanished and all that counts is the inclusion relationship between the sets.” Indeed the sets seem to vanish too. We have the opposite idea: how can we make the structure surrounding the conjecture richer?

Boolean Function Approach

We are complexity theorists, so our hammer is Boolean functions: forget lattices and graphs. We love Boolean functions. We try to see everything through properties of Boolean functions; this is both the strength of our area and its weakness. Okay, ours may be just a trivial restatement of FC: the function {f} is just the indicator function of the sets. Yet. Yet, we believe that this simple insight may help us make progress on FC. There are many equivalent statements of FC as questions about lattices, about graphs, and about other mathematical objects. What we find exciting about this statement is that it suggests two things:

  • A potential powerful set of tools from Boolean complexity theory that may shed light on FC.

  • A large class of possible weaker conjectures that we may be able to solve.

The latter echoes a motivation for the lattice and graph forms expressed in the survey—they yield interesting special cases. We can try to prove theorems like this:

Theorem: For any {f} that has property {X} in addition to FP, the FC holds.

We can prove this when {X} is the property “symmetric” or “monotone.” We wonder about other properties such as having low degree as polynomials, having read-once decision trees, and so on.

Influence Of Boolean Functions

Let {f: \{0,1\}^{n} \rightarrow \{0,1\}} be a Boolean function. The notion of the influence of the {i}th input of {f} is defined by

\displaystyle  I_{i}(f)=Pr_{x}[ f(x) \neq f(x^{i}) ],

where {x^{i}} is equal to

\displaystyle  x_{1 },\dots, x_{i-1}, \neg x_{i}, x_{i+1}, \dots, x_{n}.

Also, the probability is over {x} selected uniformly. There are many applications of this basic notion, and it is used in complexity theory in many places.

The Principle

If you see a number or a count of something, it often helps to replace it by the set of “somethings.” This yields additional information, and perhaps additional insight. Among many examples of this phenomenon in mathematics, we mention the notion of Betti numbers in topology. Named for Enrico Betti, they measure the complexity of spaces: the higher the number the more complex the connectivity of the space, roughly speaking. For example, Andy Yao used them to bound the depth of decision trees.

While Betti numbers remain useful, a major advance in topology was made when they were replaced by homology groups. These groups yield the Betti numbers but contain additional information. This ability to recover the old idea, yet yield a richer context, is what makes homology groups so powerful. See this for an interesting discussion of how Betti numbers evolved into homology groups from the 1920’s on, with Emmy Noether in a leading role.

Influence As A Set

Following our principle we plan on replacing {I_{i}(f)} as a number, by a set. Let us use {J_{i}(f)} to denote those {x} such that

\displaystyle  f(x) \neq f(x^{i}).

Obviously the following is true:

\displaystyle  \frac{|J_{i}(f)|}{2^{n}} = I_{i}(f).

There must be a better notation than {J_{i}}—we are open to suggestions. Any?

The key is the following lemma:

Lemma: Let {f(x_{1},\dots,x_{n})} be a Boolean function and let {x_{i}} be fixed. Then the Boolean inputs can be partitioned into six sets:

\displaystyle  A_{0},A_{1},B_{0},B_{1},C_{0},C_{1}.

These sets have the following properties:

  1. The variable {x_{i}} is equal to {0} on {A_{0} \cup B_{0} \cup C_{0}};

  2. The variable {x_{i}} is equal to {1} on {A_{1} \cup B_{1} \cup C_{1}};

  3. The union {A_{0} \cup A_{1}} is equal to {J_{i}};

  4. The function is always {0} on {B_{0} \cup B_{1}};

  5. The function is always {1} on {C_{0} \cup C_{1}};

  6. Finally {|A_{0}|=|A_{1}|} and {|B_{0}|=|B_{1}|} and {|C_{0}|=|C_{1}|}.

Monotable2

The key observation from this lemma is that the number of {x} such that {f(x)=1} and {x_{i}=1} is exactly

\displaystyle  |A_{1} \cap S| + |C_{1}|,

where {S} is the set of {x} so {f(x)=1}. This implies that for any {f}, it satisfies FC if and only if some decomposition has {f(x) = 1} for at least half of {A_{1}}. When {f} is monotone the next theorem makes this clear, but the hope is that FP alone can be made to imply that at least half of these {x} have {f(x)=1}.

Results for Monotone Boolean Functions

Every monotone function {f} immediately has FP, since {f(x) = 1} and {f(y) = 1} implies {f(x \vee y) = 1.} This insight says to us that the FP is a kind of weaker notion than monotone. But perhaps not too much weaker.

Theorem 3 Every monotone Boolean function satisfies FC.

Proof: Since {f} is monotone, an {x} in {A_{1}} must have {f(x)=1}. So {x_{i}} witnesses FC for {f}. This uses that one half at least of the places where {f} is {1} are when {x_{i}=1}. \Box

This also yields the following result.

Theorem 4 Every symmetric Frankl function satisfies FC.

Proof: Let {f(x)} be a non-trivial symmetric Boolean function. Let {L_{k}} be the set of all {x} so that {x} have {k} {1}‘s and {n-k} {0}‘s: these are the level sets. Since {f} is symmetric it is easy to see that for each level set either {f} is all {1} on this set or all {0}. Let {k} be the smallest such that {f} is {1} on the level {L_{k}}. Then we claim that {f} is also {1} on all level sets {L_{m}} with {m \ge k}. This claim shows that {f} is monotone and completes the proof.

So assume that {m=k+1}. Let {z} be in {L_{m}}. It is clear there are {x} and {y} both in {L_{k}} so that {x \vee y = z}. But then by the Frankl property, {f(z)=1}. Thus the claim is proved. \Box

Lattice Connections

It is interesting to try to get these results from the lattice version of FC. Given a Frankl function {f}, let

\displaystyle  S = \{0^n\} \cup \{x: f(x) = 1\}.

Given any {x,y \in S}, the least possible upper bound of {x,y \in S} is {x \vee y}, and by FP this belongs to {S}, so {S} obeys the unique-join property of lattices. If the set {L(x,y)} of lower bounds of {x} and {y} had no maximum, then there would be {u,v \in L(x,y)} such that {u \vee v \notin L(x,y)}. However, {u \vee v \in S} by FP again, and {u \vee v \in L(x,y)}, a contradiction. Thus {S} has unique meets, though {x \wedge_S y} need not equal the bitwise-AND {x \wedge y}—indeed the meet can be {0^n}. So FP always makes {S} into a lattice.

For an example, consider {f = x_1 \vee (x_2 \wedge x_3)}. This {f} is monotone, and {S} excludes only {010} and {001}.

BooleanCube

Now consider {x = 100}, {a = 011}, and {b = 110}. Then {a \wedge_S b = 000} since {010} is not in {S}, so {x \vee (a \wedge_S b) = x}. On the other hand, {x \vee a = 111} so {(x \vee a) \wedge_S b = b}. Thus {S} violates the equation

\displaystyle  (\forall x,b): x \leq b \implies (\forall a)[x \vee (a \wedge_S b) = (x \vee a) \wedge_S b],

which defines a modular lattice. Thus we have a monotone Boolean function whose lattice is not modular, hence not distributive either. However, for monotone {f}, {S} “almost” satisfies the following condition, which is dual to a condition called “lower semimodular” in the survey:

For all incomparable {a,b \in S}, if there is no element of {S} properly between {c = a \wedge_S b} and {b}, then there is no element properly between {a} and {a \vee b}.

Given {f} monotone, it follows that unless {a \wedge_S b = 0^n}, we have {f(a \wedge_S b) = 1} so {f(a \wedge b) = 1}. The if-clause then implies there must be exactly one {i} such that {b_i = 1} and {a_i = 0}. This implies that {a \vee b} flips only place {i} compared to {a}, so the then-clause also holds. Thus the only exception is when {0^n} acts as the meet, and indeed the above lattice is a counterexample with {a = 100} and {b = 011}.

We suspect that the proof method of a paper by Tetsuya Abe and Bumpei Nagano cited by the survey might overcome this exception, and hence prove the lattice version of FC in the monotone case directly in such manner, but we are not sure. All this should say something interesting about lattices, since monotonicity is such a natural Boolean property.

Open Problems

We noted that monotone Boolean functions have FP. Turned around, this says that Frankl functions generalize monotone functions. Can we hence prove complexity lower bounds on these functions?

One advantage of thinking of this as a Boolean problem is that new tools arise that might be available. Can we use the kind of Fourier methods that have worked for results on Boolean functions already? A prime example of the Boolean view being so powerful is the proof of the famous theorem of Kenneth Arrow on voting schemes.

24 Comments leave one →
  1. September 2, 2014 3:23 pm

    nice ideas as always but want to register my dislike of the term “DISEASE” to refer to excellent/ premiere open problems in scientific research (and once argued this in a CS chat room also). stand in good company wrt this, Kalai said in his comment he protests also. one of the problems on your list, P vs NP, has a $1M award recognizing its significance.

    what you really seem to be alluding to is an “unhealthy obsession” that can arise wrt these problems, and no disagreement on that (Terence Tao has more on this theme in his blog). but obsession is a psychological concept and not generally a biological one. “obsession” turns into “OCD” only in certain cases. also, there is a lot of scientific frustration over man open problems, but it has been pointed out eg by Lagarias wrt another problem you mentioned (Collatz) that its not reasonable to denigrate problems just because they seem to “mock our efforts.” obviously its a euphemism and all a bit cute & facetious and in jest, but language has power.

    my own proposal is to use the analogy that these are EVEREST problems. which havent been SUMMITED yet ie “PRE SUMMIT STATE”. and yes, it is possible that maybe what we think are maybe EVERESTS are actually OLYMPUS MONS problems. ofc this does come down to “glass half empty or half full” type classification…

    • September 2, 2014 8:29 pm

      Our feeling—at least mine after the sheer fiddliness of the dualities involved (and not involved) plus the technicalities of the lattice section took me hours on each of the four long-weekend days, let alone Dick’s time on his parts and cross-checking—is that these are more like NEVEREST problems…😉

  2. September 5, 2014 12:04 am

    It’s past my bedtime, so …, but I think J_i (f) is just the set of places where the partial differential of f with respect to x_i is 1.

    See Tables 9 and 10 in this article:

    Differential Logic and Dynamic Systems

    • September 5, 2014 12:20 am

      For example, look at f_8 (x, y), which is just the logical conjunction xy.

      In this case, \partial_x f = y.

      This mean that crossing the boundary of x will change the value of f exactly in those places where y is true.

    • September 6, 2014 10:01 am

      The “See a Number, Make a Set” (SaNMaS) principle leads to the following observation, that an arbitrary set of cells in a venn diagram or an arbitrary set of vertices in a k-dimensional cube is described a proposition or a boolean function as its fiber of 1, so the above sorts of differential operators are taking us from propositions to propositions, staying within the same datatype.

  3. September 7, 2014 9:40 am

    Re: “See this for an interesting discussion of how Betti numbers evolved into homology groups from the 1920’s on, with Emmy Noether in a leading role.”

    This link on ”this” is evidently a self-reference to the present article.

    • September 13, 2014 11:40 am

      I’m guessing this wasn’t intentional, but that you had another reference in mind?

  4. September 29, 2014 9:42 am

    I’ve been trying to work through this just to see if I understand the question.

    Sometimes people use “Boolean input” to mean one of the wires into a gate, in other words, one of the variables x_i.

    Other times people use “Boolean input” to mean one of the coordinate elements x \in \{0,1\}^n.

    I sense I may have guessed wrong somewhere.

  5. lesmathspoint claires permalink
    November 13, 2014 5:10 pm

    j’ai posté une demo sur lesmathematiques.net, mais il doit y avoir une erreur, ce serait trop beau (section graphes et combinatoire, ne lire que le dernier post, eventuellement un “resumé” de la demo quelque poste avant.
    si vous voyez une erreur dites moi!
    “lesmathspointclaires” (mon nom sur le forum;)

  6. November 25, 2014 12:32 am

    It looks like the WordPress trackback system is not working at present — I had a chat with an operator who offered to submit a ticket — in the meantime I’ll post the latest link to my Frankl series here:

    12. Frankl, My Dear : 12 | Inquiry Into Inquiry

Trackbacks

  1. Frankl, My Dear : 1 | Inquiry Into Inquiry
  2. Frankl, My Dear : 2 | Inquiry Into Inquiry
  3. Frankl, My Dear : 3 | Inquiry Into Inquiry
  4. Frankl, My Dear : 4 | Inquiry Into Inquiry
  5. Frankl, My Dear : 5 | Inquiry Into Inquiry
  6. Frankl, My Dear : 6 | Inquiry Into Inquiry
  7. Frankl, My Dear : 7 | Inquiry Into Inquiry
  8. Frankl, My Dear : 8 | Inquiry Into Inquiry
  9. Frankl, My Dear : 9 | Inquiry Into Inquiry
  10. Frankl, My Dear : 10 | Inquiry Into Inquiry
  11. Frankl, My Dear : 11 | Inquiry Into Inquiry
  12. 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