Skip to content

A Brilliant Book on Combinatorics

July 27, 2020


And Razborov’s brilliant proof method

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 {n} and consider some property of subsets {S} of {[n]}. Let {f(S)=1} exactly when {S} has the property. We can think of {f} 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 {f(S)=1} then any set {T} so that {S \subset T} still has the property. For example, {f(S)} could be that {S} includes at least half of the elements of {[n]}. It cannot be that {S} has an even number of elements. Another example is when {f} is given in disjunctive normal form (DNF),

\displaystyle  f \equiv T_1 \vee T_2 \vee \cdots T_m,

where each term {T_k} is a conjunction of variables. Each {T_k} can be regarded as a subset of {[n]}. Then {f(S) = 1} if and only if {S \supseteq T_k} for some {k}. Every monotone function also has a conjunctive normal form (CNF)

\displaystyle  f \equiv C_f = C_1 \wedge C_2 \wedge \cdots \wedge C_\ell,

where each clause {C_k} is a disjunction of variables. Then {f(S) = 1} if and only if {S \cap C_k \neq \emptyset} for all {k.} The problem is that the numbers {m} of terms and {\ell} of clauses involved may be huge. The clauses may have different sizes. Given a CNF {C} of maximum clause size {s}, we write {C^s} for the conjunction of clauses of size exactly {s} and {C^{<s}} for the rest. We similarly write {D^r} and {D^{<r}} for DNFs {D}.

The lower bound methods are on the size of a monotone circuit for {f(S)}. That is the circuit can only use gates {AND} and {OR}, but no other types of gates, especially not {NOT} gates. Of course, if {f} 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 {f} 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 {f} with small monotone circuits and {r,s > 0} we can find a CNF {C} of maximum clause size {s} and a DNF {D} of maximum term size {r} such that

\displaystyle  C \leq f \leq D \qquad\text{and also}\qquad D^{<r} \leq C^{<s}.

Moreover, {C^s} and {D^r} are small.

We have said “wrap” not “sandwich” because although {D} is the “upper slice,” the part of {D} with smaller terms—but there could be many of them—wraps around to be under the corresponding part of {C}. 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 {C} is a monotone boolean circuit that has {n} inputs and computes {f(x)} at the last gate. The method is called the approximation method because the idea is that it builds two other boolean functions {\mathsf{lower}} and {\mathsf{upper}}: for all {x} in {\{0,1\}^{n}}:

\displaystyle  \mathsf{lower}(x) \le f(x) \le \mathsf{upper}(x).

This follows a tradition in math that we often replace a complex function, {f(x)}, 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 {0<x<1},

\displaystyle  \exp(-bx^{2}) < \sin(x)/x < \exp(-x^{2}/6),

with {b \approx 0.172604}. If you have to reason about the behavior of {\sin(x)/x}, 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 {\mathsf{lower}} and {\mathsf{upper}} 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 {C^s} and {D^r.} 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 Theorem 1 we have:

\displaystyle  C^s \wedge C^{<s} \leq f \leq D^{<r} \vee D^r,

where: {C^s} and {D^r} are small, and while {C^{<s}} and {D^{<r}} might be big, we have {D^{<r} \leq C^{<s}}. The trick is to ask:

Is {C^{<s}} empty—that is, is it the trivial {1} function?

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

    \displaystyle  C^s \leq f.

    Since {C^s} is small, this is something we want. We got a small lower bound on {f} that holds for all arguments {x}.

  • If no, then it has a nontrivial clause corresponding to a set {E} of size at most {s-1}. This is where the wraparound comes in. We have:

    \displaystyle  D^{<r} \leq C^{<s} \leq E,

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

    \displaystyle  f \leq E \vee D^r.

    Now {E} is small, since it is just one clause, and {D^r} 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 {f} will give us a lower bound on {f}.

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

Theorem 2 If {f} has a monotone Boolean circuit of size {t}, then for any {r,s} such that {1 \leq r,s \leq n-1}, we can build a conjunction {C} of at most {t \cdot r^{s+1}} clauses of size exactly {s+1}, a disjunction {D} of at most {t \cdot s^{r+1}} terms of size exactly {r+1}, and a set {E} of size at most {s} such that either {C \leq f} or {f \leq D \cup E}.

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 {G}—so the variables have the form {x_{i,j}}, where {x_{i,j} = 1} means there is an edge between vertex {i} and vertex {j}, {x_{i,j} = 0} otherwise. Putting {m} as the number of vertices, the number of possible edges is {n = \binom{m}{2}}. We think of {G} as a set of edges, so {G \subseteq [n]}.

Checking for Triangles

Let {f(G)=1} hold precisely when {G} 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 {f(G)} is almost of order {m^{3}}. A side note is that the general complexity is much less via {m \times m} matrix products.

The first beauty of using the method is that you get to choose the parameters {r} and {s} with a goal {t} in mind. The {r} and {s} must be in {[1,n-1]}. The value of {t} will be a lower bound on the size of any monotone boolean circuit for {f}. The parameters {r,s} 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 {r=1} is a right choice. We will say what {s} is later but we will have {s=(\log n)^{O(1)}}. Once you pick them, the CNF {C} and DNF {D} (and small set {E}, a set of {O(\log n)} edges in this case) are chosen for you. You have no control over the sets {T_k} that make up the terms of {D} and the sets {C_\ell} that correspond to the clauses of {C}. 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 {k=1,\dots,t \cdot s^{r+1} = ts^2}, each {T_k} is of size {2}.

  2. For {\ell=1,\dots, t \cdot r^{s+1} = t}, each {C_\ell} is of size {s+1}.

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

  1. Case {f \leq D \cup E}. Here we want to consider graphs {G} that do have a triangle—and nothing else. Because {E} includes at most {s} edges, hence touches at most {2s} vertices, and {2s \ll m}, we can focus on triangles among the {m' = m - 2s} untouched vertices. There are {T = \binom{m'}{3} = \Theta(m^3)} such triangles, hence {T} graphs {G} to consider.

    Since these graphs {G} have no edges in {E} but make {f(G) = 1}, there must be some {k} such that {T_k(G) = 1}. Since {T_k} has size {2}, this means {T_k} has two edges of the triangle. Now the point is:

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

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

    \displaystyle  ts^2 \geq \binom{m'}{3}.

    Because {s = (\log n)^{O(1)}}, we finally get {t = \tilde{\Omega}(m^3)}, where the tilde means to ignore factors of {\log n}.

  2. Case {C \leq f}. Here we want to consider graphs {G} such that {f(G) = 0} but {G} is chock full of as many edges as one can have without creating a triangle. Such {G} include complete bipartite graphs. There are {2^{m-1} - 1} such graph inputs, as can be realized from how any binary string {w} except {0^m} and {1^m} encodes such a graph—and only its bit-complement {w'} encodes the same labeled graph.

    In order to keep {C \leq f} we need {C(G) = 0} for all such {G}, so we need (at least) one clause {C_k} to fail on {G}. This means that all vertices touched by the edges in {C_k} must be in the same partition. The more vertices touched, the fewer strings {w} have all {0}s (or all {1}s) in the corresponding positions, which means the fewer graphs {G} “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 {s' = \lceil \sqrt{2s}\rceil}. The number of graphs we cover is at most {2^{m - s'} - 1} (the {-1} excludes the empty graph). Thus the number {t} of clauses we need satisfies

    \displaystyle  t \geq \frac{2^{m-1} - 1}{2^{m - s'} - 1} \geq 2^{s' - 1}.

    By taking {s' > 4.5\log^2 m} we can make {t \geq m^3} in this case. We can actually get bigger functions with bigger {s}, but this balances against case 1 where {t = \tilde{\Omega}(m^3)} 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 {s} in the triangle example?

Would you prefer not changing {r} and {s} in the statement of Theorem 2? Then we would have worded the triangle example with “{r = 2}” rather than “{r = 1}.” 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 Theorem 2 somewhat messier. Another possibility was keeping Jukna’s usage throughout, so that the earlier version 1 of the theorem would say {D^{\leq r} \leq C^{\leq s}} with {C^{s+1}} and {D^{r+1}} being small. We try to solve “exposition problems” in every post but feel a dilemma here. Comments might help us on a followup post.

7 Comments leave one →
  1. Serge permalink
    July 27, 2020 9:51 am

    The most famous open exposition problem is probably to explain the proof of the four-color theorem to a human being.

  2. July 27, 2020 3:32 pm

    Re: OEPs vs. ORPs, I expressed the question once this way —

    My Thematics • 2

    Communication is so much harder
    Than mere invention or discovery.

    Will they have in mind what I have in mind?
    Will I find the signs? Will I have the time?

    There is so much shadow there must be light!

  3. July 28, 2020 3:16 pm

    Jukna’s book is one of my favorites. I read through most of it in an independent study during my undergrad. Perhaps my only criticism of the book was that the significance of the circuit applications, like this one, flew over me without further explanation by my advisor, David Barrington.
    Next you must do a post on Jukna’s other book, Boolean Function Complexity!

  4. Shankar Subramanian permalink
    July 30, 2020 6:15 am

    Thanks for introducing this. Great subject

  5. David J. Littleboy permalink
    July 31, 2020 6:02 am

    What are the textbooks that you use and/or would recommend to get students up to the point of reading this book? (I did an MS in Comp. Sci. in ’84, but have been doing mostly other things since.)

    A short list (2, at most 3) would be appreciated…

Trackbacks

  1. 极值组合技术及其在计算机科学中的应用 – HackBase
  2. A Brilliant Book on Combinatorics – Avada Forum

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s