A Brilliant Book on Combinatorics

Stasys Jukna is the author of the book Extremal Combinatorics With Applications in Computer Science .

Today we talk about Jukna’s book on extremal combinatorics.

The structure of his book is great. The material is useful and well presented. Rather than add more general comments about his book, we thought we might highlight one tiny part—the part on monotone circuit lower bounds. Here goes. All below is based directly on his discussion. Any errors or misguided comments are ours.

Monotone Boolean Functions

Fix an input size and consider some property of subsets of . Let exactly when has the property. We can think of as a Boolean function. You believe that this property is hard to compute—how do you go about proving that?

In general we have no tools, but if the property is monotone, then there are some powerful methods. Recall monotone means that if then any set so that still has the property. For example, could be that includes at least half of the elements of . It cannot be that has an even number of elements. Another example is when is given in disjunctive normal form (DNF),

where each term is a conjunction of variables. Each can be regarded as a subset of . Then if and only if for some . Every monotone function also has a conjunctive normal form (CNF)

where each clause is a disjunction of variables. Then if and only if for all The problem is that the numbers of terms and of clauses involved may be huge. The clauses may have different sizes. Given a CNF of maximum clause size , we write for the conjunction of clauses of size exactly and for the rest. We similarly write and for DNFs .

The lower bound methods are on the size of a monotone circuit for . That is the circuit can only use gates and , but no other types of gates, especially not gates. Of course, if has no small monotone circuits, then it has no small DNF or CNF formulas either.

The neat fact on which the lower-bound technique builds is that if does have small monotone circuits, then we can “wrap” it between a CNF and a DNF in various customizable ways:

Theorem 1 (informal) For every with small monotone circuits and we can find a CNF of maximum clause size and a DNF of maximum term size such that

Moreover, and are small.

We have said “wrap” not “sandwich” because although is the “upper slice,” the part of with smaller terms—but there could be many of them—wraps around to be under the corresponding part of . This fact will enable us to throw away the smaller clauses and terms. How small is “small”? We will say later. We are trying to solve problems of exposition by keeping a high-level view at the start.

Exposition Problems

Tim Gowers has written an article about the lower method for monotone functions. The method is due to Alexander Razborov in his seminal 1985 paper and extended by Noga Alon and Ravi Boppana in their paper right afterward, and by Benjamin Rossman in his 2009 paper , to name a few.

Gowers says right away that the original papers on this method are clear and well written. But he believes that there is need for more exposition. The method is so important that it must be made easy for all to understand. He says his article is an attempt to solve an open exposition problem . The notion of an exposition problem is due to Timothy Chow who wrote :

All mathematicians are familiar with the concept of an open research problem. I propose the less familiar concept of an open exposition problem.

Chow raised this issue with respect to the forcing method in set theory due to Paul Cohen. A modest suggestion: Read Chow on forcing, a great exposition; read Gowers on the monotone lower bound method, another great one. Both are much better than anything we can do. But we will put our own spin on the lower bound method. And hope to add to the quest to solve the exposition problem.

The Method—High Level

Suppose that is a monotone boolean circuit that has inputs and computes at the last gate. The method is called the approximation method because the idea is that it builds two other boolean functions and : for all in :

This follows a tradition in math that we often replace a complex function, , with simpler upper and lower bounds. Standard stuff.

Usually the point is that the approximators are not only easier to understand but also simpler in some objective sense. For example, Christophe Chesneau and Yogesh Bagul give a nice short compendium of approximating formulas involving trigonometric functions by formulas without them, including that for all ,

with . If you have to reason about the behavior of , it is nice to have these upper and lower bounds. Note that the upper bound kind-of wraps around because it is the same kind of function as the lower bound.

What gives the monotone method a special twist is that and are not necessarily simple in the sense of being small. Rather, they make simple errors —ones that can be corrected with small effort. The correction process yields and Isolating what is small, however, requires us to trade an “AND” of two inequalities for an “OR” of two economical ones. We know that at least one of the latter inequalities must be true. We arrange that either one gives us the kind of lower bound we seek.

Some More Detail

Here is how the trade happens. From Theoremwe have:

where: and are small, and while and might be big, we have . The trick is to ask:

Is empty—that is, is it the trivial function?

• If yes , then it goes away on the left-hand side. We get:

  

  Since is small, this is something we want. We got a small lower bound on that holds for all arguments .

• If no , then it has a nontrivial clause corresponding to a set of size at most

  . This is where the wraparound comes in. We have:

  

  since we chose at least one clause. Substituting on the right-hand side thus gives us:

  

  Now is small, since it is just one clause, and is small. We got a small upper bound rather than lower bound, but the fact that it has a restricted form and holds for all cases we can input to will give us a lower bound on .

Finally we are ready to state the theorem, which quantifies “small.” To follow Jukna, we now need to replace “ ” by “ ” and “ ” by “ .” But the essence is the same.

Theorem 2 If has a monotone Boolean circuit of size , then for any such that , we can build a conjunction of at most clauses of size exactly , a disjunction of at most terms of size exactly , and a set of size at most such that either or .

Rather than re-prove this, we will continue the discussion with a concrete example. An exposition trick is: give examples before the general case and then abstract. Our example will involve graphs —so the variables have the form , where means there is an edge between vertex and vertex , otherwise. Putting as the number of vertices, the number of possible edges is . We think of as a set of edges, so .

Checking for Triangles

Let hold precisely when has a triangle. This is clearly a monotone property. Our goal is to use the lower and upper bounds to prove that the monotone complexity of is almost of order . A side note is that the general complexity is much less via matrix products.

The first beauty of using the method is that you get to choose the parameters and with a goal in mind. The and must be in . The value of will be a lower bound on the size of any monotone boolean circuit for . The parameters are bounds on the clause and term size of the DNF and the CNF. You can select them any way you wish. But of course choose them wisely.

In this case we know that is a right choice. We will say what is later but we will have . Once you pick them, the CNF and DNF (and small set , a set of edges in this case) are chosen for you. You have no control over the sets that make up the terms of and the sets that correspond to the clauses of . Well you do know something about them. Here is what you do know about how many sets there are and how big the sets are:

1. For , each is of size .
2. For , each is of size .

The goal in either case is to force to be large. We’ve numbered the right-hand case first.

1. Case . Here we want to consider graphs that do have a triangle—and nothing else. Because includes at most edges, hence touches at most vertices, and , we can focus on triangles among the untouched vertices. There are such triangles, hence graphs

   to consider.

   Since these graphs have no edges in but make , there must be some such that . Since has size , this means has two edges of the triangle. Now the point is:

   For each , there is at most one triangle that can be two edges of.

   Hence there must be at least as many terms as possible triangles. This means:

   

   Because , we finally get , where the tilde means to ignore factors of .

2. Case . Here we want to consider graphs such that but is chock full of as many edges as one can have without creating a triangle. Such include complete bipartite graphs. There are such graph inputs, as can be realized from how any binary string except and encodes such a graph—and only its bit-complement encodes the same labeled graph.

   In order to keep we need for all such , so we need (at least) one clause to fail on . This means that all vertices touched by the edges in must be in the same partition. The more vertices touched, the fewer strings have all s (or all s) in the corresponding positions, which means the fewer graphs “covered” by that clause. We want to know how many clauses we need to cover all these graphs, hence we try to minimize the number of vertices touched by each clause. That number is at least . The number of graphs we cover is at most (the excludes the empty graph). Thus the number of clauses we need satisfies

   

   By taking we can make in this case. We can actually get bigger functions with bigger , but this balances against case 1 where was the best we could do, so that is our lower bound.

Open Problems

Does this help in understanding the approximation method? Can you work out the concretely optimum choice of in the triangle example?

Would you prefer not changing and in the statement of Theorem? Then we would have worded the triangle example with “ ” rather than “ .” The former is a little more suggestive of the idea of having two edges of a triangle. Doing so, however, could make notation in the proof of Theoremsomewhat messier. Another possibility was keeping Jukna’s usage throughout, so that the earlier versionof the theorem would say with and being small. We try to solve “exposition problems” in every post but feel a dilemma here. Comments might help us on a followup post.