tag:blogger.com,1999:blog-3722233.post114908044651353056..comments2024-09-16T11:29:06.673-05:00Comments on Computational Complexity: Dispersing Ramsey GraphsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-1154490311160753182006-08-01T22:45:00.000-05:002006-08-01T22:45:00.000-05:00Isn't p=2*2^(-k choose 2) instead of p=2^(-k choos...Isn't p=2*2^(-k choose 2) instead of p=2^(-k choose 2)/2?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1149165853089430272006-06-01T07:44:00.000-05:002006-06-01T07:44:00.000-05:00The "standard transformation" is this one: given a...The "standard transformation" is this one: given a potential edge (a,b) of the Ramsey graph with a \geq b, include (a,b) in the graph iff (a,b) is included in the bipartite Ramsey graph.<BR/><BR/>Then it is easy to check that the new graph has no clique or independent set of size K if the old one avoided bipartite cliques and bip. independent sets of size K/2.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1149158439687763772006-06-01T05:40:00.000-05:002006-06-01T05:40:00.000-05:00The authors point out that one can use a "standard...The authors point out that one can use a "standard transformation" to convert such a bipartite Ramsey graph to an ordinary Ramsey graph with the same parameters.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1149105105850687582006-05-31T14:51:00.000-05:002006-05-31T14:51:00.000-05:00wait, this isn't quite right.You're talking about ...wait, this isn't quite right.<BR/><BR/>You're talking about construction of Ramsey graphs on n vertices with no monochromatic clique or independent set of size k, and give bounds on that.<BR/><BR/>But the paper is talking about bipartite Ramsey graphs on n x n vertices, which are a different thing. Here we have no monochromatic sets A,B each of size k on each side of the bipartite graph such that there are no edges between A and B. It's a different thing.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1149101276030372802006-05-31T13:47:00.000-05:002006-05-31T13:47:00.000-05:00But the techiques used are very different from tho...But the techiques used are very different from those used previously, aren't they? Perhaps that's the point.Cheshire Cathttps://www.blogger.com/profile/07463645065346922684noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1149099465478045152006-05-31T13:17:00.000-05:002006-05-31T13:17:00.000-05:00An example of the kind one is looking for can perh...An example of the kind one is looking for can perhaps be provided by Vaughan Jones' fabled creation of his knot polynomial - he was working on vertex operator algebras and whence he realised that that work implied a new knot invariant. The connection was "sweet" all the more since it got him the Fields :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1149091851888755132006-05-31T11:10:00.000-05:002006-05-31T11:10:00.000-05:00Dispersers and Ramsey graphs are essentially the s...Dispersers and Ramsey graphs are essentially the same object. This is hardly an example of the kind you are looking for (a work in one area giving a result in a different area).Anonymousnoreply@blogger.com