In mathematics the art of proposing a question must be held of higher value than solving it—Georg Cantor
|
| Cropped from his page |
David Zuckerman has a beautiful result on the approximate hardness of the clique problem. His paper, “Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number,” has has received almost 1,000 citations since it was first published in 2007. Wow.
Today we discuss a possible relevance of this result for P versus NP.
Recall a clique is a subset of nodes of an undirected graph, such that every two nodes in the subset are connected by an edge. Wikipedia’s illustration below does not have large cliques—only two cliques of 
nodes shaded blue to go with a bunch of triangles shaded lighter.
Is there a relatively small change we could make to the graph to give it a much larger clique? At top right, we could add two edges to extend the blur -clique to a 
-clique—a pentagram inside a pentagon. At bottom left we could add edges to make the four triangles blossom into a 
-clique.
Computing the size of the largest clique in a graph—or just telling whether it has a clique of a given size 
—is a famous NP-complete problem. Counting the number of cliques of the largest size is evidently a harder problem still. Yet you might think it easier to tell a graph with only small cliques apart from a graph that has large ones. This is where David’s result comes in.
In passing, we note David’s place among the winners of the 1986 William Lowell Putnam Mathematical Competition. Also on the list was Bjorn Poonen, whom we have also highlighted multiple times including recently. Here is the 1986 exam; Ken and I confess we did much worse when we took the Putnam in earlier years.
David’s Result
Polynomial growth refers to a function that is bounded by 
for some constant 
. Quasi-polynomial growth means one bounded by 
for some . Let 
those sets accepted by a deterministic algorithm that runs in quasi-polynomial time and let 
be those sets accepted by a nondeterministic algorithm that runs in quasi-polynomial time
Let 
be an 
-vertex graph. We have two properties of for a fixed 
:
-
Clumpy:
has a clique of size at least 
.
-
Limpid: has no clique of size
.
The following is a main result in David’s paper:
Theorem 1 The problem of distinguishing clumpy graphs from limpid graphs is not in 
provided 
.
It is fundamentally a de-randomization result. Our idea is to scale it down in a way that may bring 
into contact with mathematical theorems that govern effects of the scaling. The theorems may be adjacent to conjectures that can suggest new approaches. The idea may require bringing back randomization, however.
The Question
Our quest to build on David’s theorem leads us to interpose a classic idea. In work with Paul Erdős, Tibor Radó wrote 
to mean that every 
-coloring of the edges of has a monochromatic subgraph 
. The classic two-color Ramsey theorem states that for all 
there is a such that 
. Erdős and George Szekeres further showed can have fewer than 
nodes.
Definition 2 Say an 
-node graph is 
-Radó if every edge 2-coloring of leaves a clique of 
vertices.
In Radó’s notation, this is if 
. The first point is that all clumpy graphs are -Radó for large enough . Taking 
puts the 
-sized clique above the Erdős-Szekeres bound for the Ramsey property to hold.
Thus the key question becomes:
Suppose that is a limpid graph. Can also be -Radó?
Suppose the answer is no. Then every limpid graph has an edge 2-coloring that does not leave a clique of size 
. We can verify this in quasi-polynomial time by trying all -subsets of the vertices.
This sets up a situation where both “limpid” and “clumpy” have an witness. More to the point, we obtain the modified problem of distinguishing “clumpy” from “not -Radó” (for appropriately chosen ). This would then likewise be -hard by David’s result. Then, we would have an -hard promise problem with promise set 
not-c-Radó belonging to . This would be a plausible unlikelihood along the lines of what the ESY conjecture, which we covered here, rules out. We can obtain a clearer unlikelihood if we relax the new definition.
Definition 3 An -node graph is almost -Radó if all but a negligible fraction of edge 2-colorings leave a monochrome clique on 
vertices.
Here “negligible” means a function asymptotically less than 
for any quasi-polynomial function 
. With some informality, we can prove:
Proposition 4 Suppose no limpid graphs are almost -Radó. Then 
is contained in randomized .
Proof: Formally, the negation is worded so that there is a quasi-polynomial function such that for every limpid graph —with the concrete value of 
and corresponding —there are a 
fraction of 2-edge-colorings of that do not have a monochromatic clique of size 
. Now define an algorithm 
that given any graph guesses order- such colorings at random.
-
If finds a coloring that does not have a monochromatic clique of size , then rejects.
-
Else, accepts.
Whenever is clumpy, will always accept. If is limpid, then with high probability, will find a coloring witnessing that is not clumpy, and will reject . Thus, distinguishes limpid from clumpy in randomized quasi-polynomial time. 
The Quest For Limpid Radó Graphs
If, like most, you believe , or further in the “ESY”-type strengthening of 
, then the answer must be that limpid (almost-)-Radó graphs exist. The question of finding them, however, has a long trail that leads back into complexity theory.
To begin, let’s decouple the clique size from the number of nodes by considering graphs with a clique of size to be “lumpy,” and use the original form of the Radó property: every 2-edge coloring has a monochrome triangle. It is surprisingly hard to find a 
-free graph with the property. Brute-force attempts for 
-node and 
-node graphs that are maximal for having no fail:
The smallest -free graph with the Radó triangle property that we know how to build has 
nodes and comes from a proof that the Radó triangle property is 
-complete. The proof is in a 1985 paper by Moon-Jung Chung, W. Michael Evangelist, and Ivan Hal Sudborough. The graph at left, which looks like a bat, is such that any 2-edge coloring without a monochrome triangle must give the two edges marked 
the same color—whichever color is used for two edges of the middle triangle.
Joining a bat and an upside-down bat creates the graph at right, in which the edges marked and 
must have opposite colors. This creates a truth-assignment gadget for each pair of literals 
and 
in a 3CNF formula 
given as instance of the -complete Not-All-Equal 3SAT problem. Using one triangle per clause of , connecting more bats between or 
appearing in the clause to the corresponding edges in the truth gadgets creates a -free graph 
that has the Radó property if and only if has an assignment making 1 or 2 literals true in each clause.
Then every negative instance induces a -free Radó graph . We can get one more simply, however, by adding a third “bat” to the graph at right above that connects and . The resulting 
-node graph has no 2-edge coloring without making a monochrome triangle.
To be truly “limpid,” however, the graph should exclude smaller cliques. The following problem of Erdős and Radó was open for some time:
Does there exist a 
-free graph with the Radó triangle property?
This was solved in 1970 by Jon Folkman and then improved in 1987 by a probabilistic argument of Joel Spencer, in a paper titled, “Three Hundred Million Points Suffice.” That’s right: for the minimum Radó criterion he showed there is a limpid graph with 
nodes. This 2007 paper by the Ramsey-theory experts Stanisław Radziszowski and Xu Xiaodong proves that the minimum possible 
is 
and gives evidence that 
is plausible. let 
stand for the least possible such .
However one such graph exists, it must give rise to a “bat”-type construction and forthwith a reduction showing the -completeness of the 
-free Radó property. Thus the Ramsey-type existence question is entangled with complexity theory. How this relationship scales up for -Radó and clumpy versus limpid graphs is the point we are driving at.
Ramsey Scaling And Complexity
There are two main levers by which we are scaling:
-
Up from the constant
of the Radó triangle property to 
for -Radó.
-
Up to
as the allowed clique size in a limpid graph.
The latter corresponds to the size for clumpy that we are distinguishing, but there is some freedom in . If we imagine and 
as fixed—temporarily ignoring the dependence on —we can ask, what is the minimum size 
of a -limpid graph that is -Radó?
To avoid a complexity collapse, we must bet on at worst a single-exponential dependence on , polynomial in . Can we possibly show this directly? Note that 
, 
already raised the specter of in the hundred millions. Not only do we not see a way to scale up Spencer’s proof, he remarked in the intro that his proof is “extremely case specific” and does not scale even to 3-edge colorings. The “almost” feature of Definition 3 adds a further complication.
It may be that the guiderails for ascending to higher and (scaling with the number of nodes) are already present among the details of the graph constructions in David’s proof and the proofs of the theorems his paper builds on. We have not had time to delve. There must be some connection; the question is whether complexity considerations take the lead or follow only in train of the sides that can be mathematically disproved. Other connections of Ramsey theory are in this nice 2004 survey by Vera Rosta.
Here is one more indication of why we think the interaction between complexity and Ramsey theory can be nontrivial. Putting 
, the upper bound noted above for the diagonal- Ramsey number has rough order 
. The best known lower bound has rough order 
. Can we show an impact of the growth of 
on complexity theory, in advance of resolving this gap which has been open for over fifty years?
Open Problems
The key issue is, what about the above question? Assuming the usual belief that quasi-polynomial time and nondeterministic quasi-polynomial time are distinct we must be able to show a fact about -colorings of clumpy and limpid graphs. If this is hard to prove, then we have an interesting impasse. Even worse, if this is false, then our beliefs collapse.
The feature that surprises us about the 1986 Putnam exam is that it does not have a question that involves the number 1,986. Ken and I both remember such features. Here is a problem they could have used; we will give the answer later:
Alan and Barbara play a game in which they take turns filling entries of an initially empty 1986 x 1986 array. Alan plays first. At each turn, a player chooses a real number and places it in a vacant entry. The game ends when all the entries are filled. Alan wins if the determinant of the resulting matrix is nonzero; Barbara wins if it is zero. Which player has a winning strategy?
The answer is at the end of the next post.
[removed reference to Putnam ranking, “batch”->”bats” in the proof from 1985, added answer link for puzzle at end]
Like this:
Like Loading...
Related
I’m very surprised that this post hasn’t received any comments yet. I think that there is a simple probabilistic construction that shows that there are limpid c-Rado graphs, but I haven’t done all the calculations rigorously and I don’t claim to be an expert. The idea is to simply take a random graph G where we delete each edge with probability n^t, so each edge is in G with probability 1-n^t. If t is about -epsilon, then whp G will be limpid, i.e., omega(G)<n^epsilon. On the other hand, for any red-blue coloring of the edges of G, we can repeat the standard proof of Ramsey's theorem. That is, at any given step, we pick an arbitrary x, see whether it has more red or blue neighbors, and recurse in the rest of the graph. Since t was small, at any point when there are m vertices left, the degree of x will be almost m, so the size of the graph is almost halved. Of course some probabilistic calculations are needed at the end, but I think they will be fine.
ps. Do you know the answer to the Putman style problem at the end for odd numbers?
Putnam fellows are listed in alphabetical order of last name. Relative ranking of Putnam fellows is never officially disclosed.
Barbara has a winning strategy: for all her steps other than the last one, fill in a random real from [0,1] in an arbitrary unfilled square. For her last step, with probability one, there is a unique value that will make the matrix singular.
I think that this argument is incorrect. Suppose that B always picks her unfilled squares from the upper-right triangle, while A is filling out the lower-left with 0’s. Moreover, A also puts a 0 on the main diagonal, which otherwise can be filled by B. Then if B’s last square is the top-left corner, she cannot influence the determinant. Moreover, this is also true if A puts a non-0 value (instead of a 0 value) to right under the top-left corner. This way A can ensure that the determinant is non-0.
For this last statement, we also need that A puts his 0 on the second element of the main diagonal. For example, they might end up with a matrix like this:
1111
1011
0011
0001
OK, there’s an even simpler argument. Suppose that B always picks her unfilled squares from the upper-right triangle, while A is filling out the lower-left with 0’s. Suppose further that they mutually fill in the diagonals with non-0 values. Then if the last element left for B is not on the diagonal, she cannot influence the singularity.
Another question about graphs which have cliques: Suppose you pick a random graph, with some fixed edge density. If it has a clique, is it also more likely to have an anti-clique? Clearly, if the edge density is high, then it’s more likely to have a clique.
But suppose you limit to, say, a randomly-chosen graph G with exactly half of the possible edges. If G has a clique of some size, is it more likely to have an anti-clique of that size?
I have a vague intuition that it does, because if there’s a clique, then the edges are “concentrated” in that clique, so that the density of edges outside the clique is lower, making an anti-clique more likely. But that’s only an intuition.
(I couldn’t find this question in thirty-seconds-of-searching, but haven’t looked very thoroughly.)