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.

Who Invented Pointers, Amortized Complexity, And More?

August 26, 2014

Some algorithmic tricks were first invented in complexity theory

Screen Shot 2014-08-26 at 4.00.14 PM

Andrey Kolmogorov, Fred Hennie, Richard Stearns, and Walter Savitch are all famous separately; but they have something in common. Read on, and see.

Read more…

Why Is 290 Special?

August 23, 2014
by


How exceptions in theorems may affect their complexity

BhargavaindiaToday
Cropped from India Today source

Manjul Bhargava is a mathematician who just won one of the 2014 Fields Medals. We offer our congratulations on this achievement. He is an expert in number theory, which makes him special to us among Fields medalists. His Fields citation includes his doctoral work on a powerful reformulation and extension of Carl Gauss’s composition law for quadratic forms. He also proved a sense in which 290 is special to us among numbers, since we have been thinking recently about quadratic forms as tools in complexity theory.

Today we talk about his “290 Theorem” with Jonathan Hanke, which is quite accessible, and also raise complexity-related questions about this result. Read more…

The Derivative Of A Number

August 19, 2014

Are you kidding?

Unknown

Edward Barbeau is now a professor emeritus of mathematics at the University of Toronto. Over the years he has been working to increase the interest in mathematics in general, and enhancing education in particular. He has published several books that are targeted to help both students and teachers see the joys of mathematics: one is called Power Play; another Fallacies, Flaws and Flimflam; and another After Math.

Today I want to discuss his definition of the derivative of a number, yes a number.
Read more…

The 3SUM Assumption Is Wrong?

August 16, 2014


A new result on our three body problem

Screen Shot 2014-08-16 at 11.16.19 AM

Allan Grønlund and Seth Pettie are leaders in algorithm design and related problems.

Today I want to give a quick follow up on our discussion of 3SUM based on a recent paper of theirs. Read more…

Our Three Body Problem

August 13, 2014


The three body problem, computer theory style

Unknown

Ellis Horowitz is one of the founders of the theory of algorithms. His thesis with George Collins in 1969 had the word “algorithm” in the title: “Algorithms for Symbolic Integration of Rational Functions.” He is known for many things, including an algorithm that after forty years is still the best known.

Today I want to talk about this algorithm, and one of the most annoying open problems in complexity theory. Read more…

Laplace’s Demon

August 8, 2014


Demons and other curiosities

Unknown

Pierre-Simon Laplace was a French scientist, perhaps one of the greatest ever, French or otherwise. His work affected the way we look at both mathematics and physics, among other areas of science. He may be least known for his discussion of what we now call Laplace’s demon.

Today I want to talk about his demon, and whether predicting the future is possible.

Can we predict the past? Can we predict the present? Can we predict the future? Predicting the past and predicting the present sound a bit silly. The usual question is: Can we predict the future? Although I think predicting the past—if taken to mean “what happened in the past?”—is not so easy.

Read more…

Follow

Thank you for subscribing “Gödel's Lost Letter and P=NP”

You’ll get an email with a link to confirm your sub. If you don’t get it, please contact us