Enriching the Frankl Conjecture

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 of subsets of a finite set is closed under union, then there is an element of that belongs to at least half of the sets in the family.

One may suppose that the always belongs to the union-closed family. The “half” is tight, as follows on considering the power set of 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 on :

The Frankl Conjecture (FC) property then reads: there is an such that at least half of the satisfying assignments have . The conjecture itself then states:

If has FP, then it satisfies FC.

The survey actually emphasizes the dual form, which in our terms involves the function , where is the bit-flip of . FP becomes , 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 such that at most half the satisfying assignments of have . 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 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 ) 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 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 that has property in addition to FP, the FC holds.

We can prove this when 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 be a Boolean function. The notion of the influence of the th input of is defined by

where is equal to

Also, the probability is over 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 as a number, by a set. Let us use to denote those such that

Obviously the following is true:

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

The key is the following lemma:

Lemma: Let be a Boolean function and let be fixed. Then the Boolean inputs can be partitioned into six sets:

These sets have the following properties:

1. The variable is equal to on ;

2. The variable is equal to on ;

3. The union is equal to ;

4. The function is always on ;

5. The function is always on ;

6. Finally and and .

The key observation from this lemma is that the number of such that and is exactly

where is the set of so . This implies that for any , it satisfies FC if and only if some decomposition has for at least half of . When 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 have .

Results for Monotone Boolean Functions

Every monotone function immediately has FP, since and implies 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 is monotone, an in must have . So witnesses FC for . This uses that one half at least of the places where is are when .

This also yields the following result.

Theorem 4 Every symmetric Frankl function satisfies FC.

Proof: Let be a non-trivial symmetric Boolean function. Let be the set of all so that have ‘s and ‘s: these are the level sets. Since is symmetric it is easy to see that for each level set either is all on this set or all . Let be the smallest such that is on the level . Then we claim that is also on all level sets with . This claim shows that is monotone and completes the proof.

So assume that . Let be in . It is clear there are and both in so that . But then by the Frankl property, . Thus the claim is proved.

Lattice Connections

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

Given any , the least possible upper bound of is , and by FP this belongs to , so obeys the unique-join property of lattices. If the set of lower bounds of and had no maximum, then there would be such that . However, by FP again, and , a contradiction. Thus has unique meets, though need not equal the bitwise-AND —indeed the meet can be . So FP always makes into a lattice.

For an example, consider . This is monotone, and excludes only and .

Now consider , , and . Then since is not in , so . On the other hand, so . Thus violates the equation

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

For all incomparable , if there is no element of properly between and , then there is no element properly between and .

Given monotone, it follows that unless , we have so . The if-clause then implies there must be exactly one such that and . This implies that flips only place compared to , so the then-clause also holds. Thus the only exception is when acts as the meet, and indeed the above lattice is a counterexample with and .

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.