tag:blogger.com,1999:blog-3722233.post7523852952350008481..comments2023-12-07T03:00:23.146-06:00Comments on Computational Complexity: A slightly diff take on Lipton's use of Ramsey's TheoremLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-3722233.post-63975369259030002142011-07-22T08:06:42.541-05:002011-07-22T08:06:42.541-05:00Sorry about the confusion in the previous two post...Sorry about the confusion in the previous two posts.<br /> <br />Let’s regroup with the following observations:<br /><br />1.Minimal coloring algorithms and clique finding algorithms can be very similar, but close only counts in horseshoes.<br /><br />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.<br /> <br />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.<br /> <br />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.<br /><br />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.<br /><br />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.<br /><br />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.<br /><br />8. To check for the fourth coordinate, we would have to add a step:<br /><br />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. <br /><br />9. I am “reasonably certain” many of these observations are more or less correct most of the time, maybe.Jim Blairnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31674117685922135392011-07-21T09:58:43.997-05:002011-07-21T09:58:43.997-05:00Houston, we may have a problem.
The second coordi...Houston, we may have a problem.<br /><br />The second coordinate could do a 2-2 split on a clique of 4.<br /><br />Back to the drawing board to see if the argument holds for cliques of 9.<br /><br />Note to Self: Nothing is 100% certain in the weird and wacky world of quixotic, quirky quanta.Jim Blairnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61139589875718008392011-07-21T07:02:37.759-05:002011-07-21T07:02:37.759-05:00Here is an observation that clique hunters might f...Here is an observation that clique hunters might find useful and/or amusing.<br />If you did a Recursive Coordinate Assignment on a clique of seven countries, you would generate the following addresses:<br />1st Country: (0,0,0,0,0,0,0);<br />2nd Country: (1,0,0,0,0,0,0);<br />3rd Country: (1,1,0,0,0,0,0);<br />4th Country: (1,1,1,0,0,0,0);<br />5th Country: (1,1,1,1,0,0,0);<br />6th Country: (1,1,1,1,1,0,0);<br />7th Country: (1,1,1,1,1,1,0);<br />If you dispense with commas, parentheses, and repeating, trailing zeroes; you have the lower half of an adjacency matrix:<br />0<br />10<br />110<br />1110<br />11110<br />111110<br />1111110<br />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.<br />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.<br />At a minimum, one of the two regions would have to contain a clique of four which would generate the 4th coordinate.Jim Blairnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73115545854918580702011-07-20T07:50:17.104-05:002011-07-20T07:50:17.104-05:00Take a look at the "Eight Coloring Riddle&quo...Take a look at the "Eight Coloring Riddle" I posted on Godel's Lost Letter under Time Chunks and Theory Nuggets.<br /><br />One trick is to use cliques to find cliques.Jim Blairnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16363198470427379832011-07-15T09:53:19.472-05:002011-07-15T09:53:19.472-05:00Anonymous above, why do you NOT capitalize words a...Anonymous above, why do you NOT capitalize words and why DO YOU over-exaggerate your claims?The Other Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25919590278828536942011-07-14T22:49:27.671-05:002011-07-14T22:49:27.671-05:00Conjecture is false. Oh well. Is there some intere...Conjecture is false. Oh well. Is there some interesting set of graphs where its true?GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20088014126574434702011-07-14T21:45:09.957-05:002011-07-14T21:45:09.957-05:00Why do you capitalize every other word in all of y...Why do you capitalize every other word in all of your posts?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36537868518935906462011-07-14T16:29:54.180-05:002011-07-14T16:29:54.180-05:00I like the idea, but the conjecture is clearly fal...I like the idea, but the conjecture is clearly false. <br /><br />Consider the following two graphs on n vertices: <br /><br />G_1 consists of a clique of order n^{delta_2} <br /><br />G_2 is a random graph, each edge picked with probability say 1-1/(log n)^{100}. <br /><br />The clique number of G_1 is large, while the clique number of G_2 is only of order polylog n (whp). <br /><br />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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81675932307682020992011-07-14T11:35:05.566-05:002011-07-14T11:35:05.566-05:00AH- I used the term ``almost all graphs G''...AH- I used the term ``almost all graphs G''<br />to mean ``all but a finite number of graphs'',<br />so not a probability thing.<br /><br />I will correct it in the post.<br /><br />Does that clear it up?GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47631724737124859052011-07-14T11:25:56.810-05:002011-07-14T11:25:56.810-05:00There's something I don't understand about...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. <br /><br />I fully expect that the misunderstanding is mine, but I haven't managed to work out what it is.Anonymousnoreply@blogger.com