ω(G) is the size of max clique in G.
Recall that, for all 0 < δ1 < δ2 < 1, the following problem is NP-hard: Given a graph G with the PROMISE that either ω(G) ≤ nδ1 OR ω(G) ≥ nδ2, determine which one it is. Output NO in the first case and YES in the second case. (Reference: David Zuckerman proved the result here by derandomizing a result of Johan Hastad that had as its conclusion ZPP=NP rather than P=NP. See here for Hastad paper.)
Note the following,
If ω(G) ≥ nδ2 then, by Ramsey's Theorem and the current bounds known on the Ramsey numbers, for ANY 2-coloring of the edges of G there will be a mono clique of size (0.5)*(δ2)log n. (Slightly larger values can also be obtained.)This gives rise to the following POSSIBLE RTIME(nO(log n)) algorithm for the promise problem.
- Input G
-
Do the following nAlog n times Or until you get a NO.
(A is a constant that we pick later.)
- Randomly 2-color the edges of G
- Look for a mono clique of size (0.5)*(δ2)log n. (This takes nO(log n) time.)
- If you DO NOT find one then output NO and stop. (In this case you KNOW the answer is NO.)
- Otherwise try again.
- (If you got here then every coloring you tried had a mono clique of size (0.5)*(δ2)log n.) Output YES. (You are NOT SURE that this is correct.)
- IF ω(G) ≥ nδ2 then the algorithm will correctly say YES.
- IF ω(G) ≤ nδ1 then will the algorithm find a coloring that shows this? Or more precisely, will this happen with high prob?
There exists 0 < δ1 < δ2 < 1, A, and a function p(n) = nAlog n such that the following is true: For almost all graphs G with ω(G) ≤ nδ1 the prob that a rand 2-coloring of the edges will have a mono clique of size (0.5)*(δ2)log n is LESS THAN (1-p(n)). (ADDED LATER: Almost All Graphs means for all but a FINITE number of graphs.)So, what to make of this?
- One MAY think the following; Since we DO NOT think that NP is in RTIME(nO(log n)) the conjecture is false. Perhaps it can be PROVEN false (unconditionally) using the techniques of Zuckerman or Hastad, or other techniques in the area.
- Is our confidence that NP is not in RTIME(nO(log n)) SO STRONG? We could at least TRY to prove the conjecture.
- One could put the correct Ramsey Number, and a good set of coin flips, into an advice string. This would yield an algorithm in DTIME(nlog n)/poly. A slighly weaker conjecture would suffice to prove this algorithm works.
There's something I don't understand about the conjecture. It seems to me that almost all graphs have clique number much smaller than a power of n, so conditioning in the way you do makes no difference. So your conjecture is equivalent to saying that for almost all graphs the probability that ... etc., which in turn is equivalent to saying that the probability that a random graph with edge-probability 1/2 has a mono clique of the size you say is less than 1-p(n), which is clearly false.
ReplyDeleteI fully expect that the misunderstanding is mine, but I haven't managed to work out what it is.
AH- I used the term ``almost all graphs G''
ReplyDeleteto mean ``all but a finite number of graphs'',
so not a probability thing.
I will correct it in the post.
Does that clear it up?
I like the idea, but the conjecture is clearly false.
ReplyDeleteConsider the following two graphs on n vertices:
G_1 consists of a clique of order n^{delta_2}
G_2 is a random graph, each edge picked with probability say 1-1/(log n)^{100}.
The clique number of G_1 is large, while the clique number of G_2 is only of order polylog n (whp).
From a random coloring perspective (or even from the Ramsey perspective), G_2 behaves much like K_n as almost all subsets of order 100log n are cliques, and all (not too small) subsets have edge density almost 1.
Why do you capitalize every other word in all of your posts?
ReplyDeleteConjecture is false. Oh well. Is there some interesting set of graphs where its true?
ReplyDeleteAnonymous above, why do you NOT capitalize words and why DO YOU over-exaggerate your claims?
ReplyDeleteTake a look at the "Eight Coloring Riddle" I posted on Godel's Lost Letter under Time Chunks and Theory Nuggets.
ReplyDeleteOne trick is to use cliques to find cliques.
Here is an observation that clique hunters might find useful and/or amusing.
ReplyDeleteIf you did a Recursive Coordinate Assignment on a clique of seven countries, you would generate the following addresses:
1st Country: (0,0,0,0,0,0,0);
2nd Country: (1,0,0,0,0,0,0);
3rd Country: (1,1,0,0,0,0,0);
4th Country: (1,1,1,0,0,0,0);
5th Country: (1,1,1,1,0,0,0);
6th Country: (1,1,1,1,1,0,0);
7th Country: (1,1,1,1,1,1,0);
If you dispense with commas, parentheses, and repeating, trailing zeroes; you have the lower half of an adjacency matrix:
0
10
110
1110
11110
111110
1111110
If you hid a clique of seven countries on a planar map of 700 countries, you would have a 1% chance of finding it right away. Otherwise, you would have to tediously perform the eight coloring algorithm until you found a region that requires a 4th coordinate.
The chances of finding it are 100%. If the lowest value of the first coordinate assigned to any member of the clique is x=a, then every other member would have to be assigned x=a or x=a+1.
At a minimum, one of the two regions would have to contain a clique of four which would generate the 4th coordinate.
Houston, we may have a problem.
ReplyDeleteThe second coordinate could do a 2-2 split on a clique of 4.
Back to the drawing board to see if the argument holds for cliques of 9.
Note to Self: Nothing is 100% certain in the weird and wacky world of quixotic, quirky quanta.
Sorry about the confusion in the previous two posts.
ReplyDeleteLet’s regroup with the following observations:
1.Minimal coloring algorithms and clique finding algorithms can be very similar, but close only counts in horseshoes.
2.One way to set-up a deductive reduction from eight to six colors is to pick z-origins in a non-random way as we move away from the y-origin.
3.The key rule is pick “the one and only country” in an (x=a, y=b) group that touches a pair of countries in the (x=a, y=b-1) group to be the z-origin, if that country exists.
4.If we are worried about a hidden clique of seven, we would have to add a step. Keep checking after finding the first z-origin to see if there is a second candidate and red flag it as violating planarity.
5. It is probably possible to draw the 700 country map with the clique of seven on a topological surface (genus 2 or above)in such a way that all seven members of the clique could be in the same x=a group.
6. In short, we have to consider all the possible ways to split the clique between x=a and x=a+1 groups: 0-7, 1-6, 2-5, and 3-4.
7. Any clique of five or more in the same x=a group would trigger a fourth coordinate. Also any clique of 3 or more in the same (x=a, y=b) group would trigger a fourth coordinate.
8. To check for the fourth coordinate, we would have to add a step:
For each group of countries where x=a, y=b, and z=c pick a country at random. Call it the origin of the w-coordinate. Assign it a w-coordinate, w=0. Do a Recursive Coordinate Assignment of the w-coordinate for all the countries in the group where x=a, y=b and z=c. The w-coordinate assigned to a country should be the smallest number of lines that would be crossed traveling from the origin of the w-coordinate to every country in the group thru the group of countries where x=a, y=b and z=c.
9. I am “reasonably certain” many of these observations are more or less correct most of the time, maybe.