A Brilliant Book on Combinatorics

栏目: IT技术 · 发布时间: 4年前

内容简介:Stasys Jukna is the author of theToday we talk about Jukna’s book on extremal combinatorics.

And Razborov’s brilliant proof method

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 A Brilliant Book on Combinatorics of A Brilliant Book on Combinatorics . Let A Brilliant Book on Combinatorics exactly when A Brilliant Book on Combinatorics 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 A Brilliant Book on Combinatorics then any set A Brilliant Book on Combinatorics so that A Brilliant Book on Combinatorics still has the property. For example, A Brilliant Book on Combinatorics could be that A Brilliant Book on Combinatorics includes at least half of the elements of A Brilliant Book on Combinatorics . It cannot be that A Brilliant Book on Combinatorics has an even number of elements. Another example is when is given in disjunctive normal form (DNF),

A Brilliant Book on Combinatorics

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

A Brilliant Book on Combinatorics

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

The lower bound methods are on the size of a monotone circuit for A Brilliant Book on Combinatorics . That is the circuit can only use gates A Brilliant Book on Combinatorics and A Brilliant Book on Combinatorics , but no other types of gates, especially not A Brilliant Book on Combinatorics 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 A Brilliant Book on Combinatorics we can find a CNF A Brilliant Book on Combinatorics of maximum clause size and a DNF A Brilliant Book on Combinatorics of maximum term size such that

A Brilliant Book on Combinatorics

Moreover, A Brilliant Book on Combinatorics and A Brilliant Book on Combinatorics are small.

We have said “wrap” not “sandwich” because although A Brilliant Book on Combinatorics is the “upper slice,” the part of A Brilliant Book on Combinatorics with smaller terms—but there could be many of them—wraps around to be under the corresponding part of A Brilliant Book on Combinatorics . 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 A Brilliant Book on Combinatorics is a monotone boolean circuit that has inputs and computes A Brilliant Book on Combinatorics at the last gate. The method is called the approximation method because the idea is that it builds two other boolean functions A Brilliant Book on Combinatorics and A Brilliant Book on Combinatorics : for all in A Brilliant Book on Combinatorics :

A Brilliant Book on Combinatorics

This follows a tradition in math that we often replace a complex function, A Brilliant Book on Combinatorics , 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 A Brilliant Book on Combinatorics ,

A Brilliant Book on Combinatorics

with A Brilliant Book on Combinatorics . If you have to reason about the behavior of A Brilliant Book on Combinatorics , 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 A Brilliant Book on Combinatorics and A Brilliant Book on Combinatorics 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 A Brilliant Book on Combinatorics and A Brilliant Book on Combinatorics 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:

A Brilliant Book on Combinatorics

where: A Brilliant Book on Combinatorics and A Brilliant Book on Combinatorics are small, and while A Brilliant Book on Combinatorics and A Brilliant Book on Combinatorics might be big, we have A Brilliant Book on Combinatorics . The trick is to ask:

Is A Brilliant Book on Combinatorics empty—that is, is it the trivial function?

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

    A Brilliant Book on Combinatorics

    Since A Brilliant Book on Combinatorics 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 A Brilliant Book on Combinatorics of size at most A Brilliant Book on Combinatorics

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

    A Brilliant Book on Combinatorics

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

    A Brilliant Book on Combinatorics

    Now A Brilliant Book on Combinatorics is small, since it is just one clause, and A Brilliant Book on Combinatorics 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 “ A Brilliant Book on Combinatorics ” and “ ” by “ A Brilliant Book on Combinatorics .” But the essence is the same.

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

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 A Brilliant Book on Combinatorics —so the variables have the form A Brilliant Book on Combinatorics , where A Brilliant Book on Combinatorics means there is an edge between vertex and vertex , A Brilliant Book on Combinatorics otherwise. Putting as the number of vertices, the number of possible edges is A Brilliant Book on Combinatorics . We think of A Brilliant Book on Combinatorics as a set of edges, so A Brilliant Book on Combinatorics .

Checking for Triangles

Let A Brilliant Book on Combinatorics hold precisely when A Brilliant Book on Combinatorics 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 A Brilliant Book on Combinatorics is almost of order A Brilliant Book on Combinatorics . 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 A Brilliant Book on Combinatorics . 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 A Brilliant Book on Combinatorics is a right choice. We will say what is later but we will have A Brilliant Book on Combinatorics . Once you pick them, the CNF A Brilliant Book on Combinatorics and DNF A Brilliant Book on Combinatorics (and small set A Brilliant Book on Combinatorics , a set of A Brilliant Book on Combinatorics edges in this case) are chosen for you. You have no control over the sets A Brilliant Book on Combinatorics that make up the terms of A Brilliant Book on Combinatorics and the sets A Brilliant Book on Combinatorics that correspond to the clauses of A Brilliant Book on Combinatorics . 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 A Brilliant Book on Combinatorics , each A Brilliant Book on Combinatorics is of size .
  2. For A Brilliant Book on Combinatorics , each A Brilliant Book on Combinatorics is of size A Brilliant Book on Combinatorics .

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

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

    to consider.

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

    For each A Brilliant Book on Combinatorics , there is at most one triangle that A Brilliant Book on Combinatorics can be two edges of.

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

    A Brilliant Book on Combinatorics

    Because A Brilliant Book on Combinatorics , we finally get A Brilliant Book on Combinatorics , where the tilde means to ignore factors of A Brilliant Book on Combinatorics .

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

    In order to keep A Brilliant Book on Combinatorics we need A Brilliant Book on Combinatorics for all such A Brilliant Book on Combinatorics , so we need (at least) one clause A Brilliant Book on Combinatorics to fail on A Brilliant Book on Combinatorics . This means that all vertices touched by the edges in A Brilliant Book on Combinatorics 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 A Brilliant Book on Combinatorics “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 A Brilliant Book on Combinatorics . The number of graphs we cover is at most A Brilliant Book on Combinatorics (the A Brilliant Book on Combinatorics excludes the empty graph). Thus the number of clauses we need satisfies

    A Brilliant Book on Combinatorics

    By taking A Brilliant Book on Combinatorics we can make A Brilliant Book on Combinatorics in this case. We can actually get bigger functions with bigger , but this balances against case 1 where A Brilliant Book on Combinatorics 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 “ A Brilliant Book on Combinatorics ” rather than “ A Brilliant Book on Combinatorics .” 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 A Brilliant Book on Combinatorics with A Brilliant Book on Combinatorics and A Brilliant Book on Combinatorics being small. We try to solve “exposition problems” in every post but feel a dilemma here. Comments might help us on a followup post.


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

妙趣横生的算法

妙趣横生的算法

杨峰 / 清华大学出版社 / 2010-4 / 49.00元

《妙趣横生的算法(C语言实现)》理论与实践相结合,旨在帮助读者理解算法,并提高C语言编程能力,培养读者的编程兴趣,并巩固已有的C语言知识。全书分为2个部分共10章,内容涵盖了编程必备的基础知识(如数据结构、常用算法等),编程实例介绍,常见算法和数据结构面试题等。《妙趣横生的算法(C语言实现)》最大的特色在于实例丰富,题材新颖有趣,实用性强,理论寓于实践之中。通过《妙趣横生的算法(C语言实现)》的学......一起来看看 《妙趣横生的算法》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换