Enriching the Frankl Conjecture
See a number, make a set
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:
- The variable is equal to on ;
- The variable is equal to on ;
- The union is equal to ;
- The function is always on ;
- The function is always on ;
- 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.
Trackbacks
- 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
- Open Problems That Might Be Easy | Gödel's Lost Letter and P=NP
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…
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… 😉
It’s past my bedtime, so …, but I think is just the set of places where the partial differential of with respect to is 1.
See Tables 9 and 10 in this article:
Differential Logic and Dynamic Systems
For example, look at which is just the logical conjunction
In this case,
This mean that crossing the boundary of will change the value of exactly in those places where is true.
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 -dimensional cube is described a proposition or a boolean function as its fiber of so the above sorts of differential operators are taking us from propositions to propositions, staying within the same datatype.
… is described by a proposition …
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.
I’m guessing this wasn’t intentional, but that you had another reference in mind?
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
Other times people use “Boolean input” to mean one of the coordinate elements
I sense I may have guessed wrong somewhere.
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;)
That domain name appears to have expired.
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
Interesting post, just saw it. I’ve recently uploaded to arxiv a paper which shows that if is a union-closed family of subsets of , and , for some small absolute constant , then the Frankl conjecture holds for . The methods I use their are boolean-analysis methods, after reformulating the problem in terms of boolean functions, as you’ve mentioned in your post.
If we look at boolean functions , where we identify the union-closed family with the inverse image of , then the Frankl-Conjecture is equivalent to saying that for some , . This is equivalent to your condition.
It does seem, however, that spectral techniques become harder to use if the union-closed family is small compared to , the size of the universe.