tag:blogger.com,1999:blog-3722233.post4951420787206539360..comments2021-12-06T22:20:37.890-06:00Comments on Computational Complexity: A "well known" theoremLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-42763176121575464822008-11-20T04:15:00.000-06:002008-11-20T04:15:00.000-06:00This comment has been removed by the author.zenzikehttps://www.blogger.com/profile/10898322552057838828noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56019660112077933402008-11-18T13:51:00.000-06:002008-11-18T13:51:00.000-06:00Hi,Does this work?Let v be the size of the larges...Hi,<BR/><BR/>Does this work?<BR/><BR/>Let v be the size of the largest cycle in the graph. We can create two cycles from this with an edge which splits it in two halfs. Each of these has size v/2. Any other edge insertion leads to a cycle of length less than v/2. And so we proceed, producing two cycles from each which are half it's size. <BR/><BR/>Since we have at most s edges to add after the initial cycle, the min depth of this binary tree is log s.<BR/><BR/>hmmmm, it's not quite finished ...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79743136310671507342008-11-18T02:40:00.000-06:002008-11-18T02:40:00.000-06:00Sorry, but I've been holding back for a few months...Sorry, but I've been holding back for a few months now so I'll just go ahead and ask, even if it's off-topic :)<BR/><BR/>Is there some hidden reason why you keep saying <I>its</I> instead of <I>it's</I>?rgrighttps://www.blogger.com/profile/02991214367108471744noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77542635006013492222008-11-17T23:14:00.000-06:002008-11-17T23:14:00.000-06:00I remember this being a homework exercise in under...I remember this being a homework exercise in undergraduate algorithms at Berkeley. Does that count as "well known"Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20825759345287166172008-11-17T16:17:00.000-06:002008-11-17T16:17:00.000-06:00Kurt: Thanks :) For some reason I didn't consider ...Kurt: Thanks :) For some reason I didn't consider that, I just checked it wasn't base e.Sagehttps://www.blogger.com/profile/04366437514587382136noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34707845794923624812008-11-17T16:16:00.000-06:002008-11-17T16:16:00.000-06:00For sage: the base for the log function is 2.For sage: the base for the log function is 2.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35527302714178723532008-11-17T16:09:00.000-06:002008-11-17T16:09:00.000-06:00Sorry, link was too long, here's a tiny URL:http:/...Sorry, link was too long, here's a tiny URL:<BR/><BR/>http://tinyurl.com/6en2p5Sagehttps://www.blogger.com/profile/04366437514587382136noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58460494829935731842008-11-17T16:06:00.000-06:002008-11-17T16:06:00.000-06:00I'm sure I'm not following something here. Anonymo...I'm sure I'm not following something here. Anonymous's proof doesn't seem to prove anything to me (but I might just not understand it) and this graph seems to disprove the original statement: http://farm4.static.flickr.com/3029/3039376406_bf1145c2b6_o.gif<BR/> (As pictured it's directed, but the result is the same if it's considered undirected and the cycle does not repeat an edge.)<BR/><BR/>That graph should have a cycle of length 2(log 10) = 2 by the above statement, but it does not. I'm guessing either I'm missing something the definition of some term, or there's some context to the originally quoted statement that provides additional conditions. It's been a while since I touched graph theory, so I'm sure I screwed something up, but this will haunt me if I can't figure out HOW I'm wrong.Sagehttps://www.blogger.com/profile/04366437514587382136noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23343226269272341892008-11-17T15:16:00.000-06:002008-11-17T15:16:00.000-06:00It is well known that is that it may be well known...<I>It is well known that is that it may be well known to people who know it (duh) but not to others.</I><BR/><BR/>This reminds me a paper I saw once as a PC chair. It went out to four reviewers, two of them world-experts in the field, the other two familiar with the subject but not experts.<BR/><BR/>The familiar-but-not-expert reviewers said the result was new and interesting, clear accept.<BR/><BR/>The world-experts said: "this is well known, not worth publishing", clear reject.<BR/><BR/>So question to the readers out there, what would should the decision be in this case: accept or reject?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12309678195520692902008-11-17T15:07:00.000-06:002008-11-17T15:07:00.000-06:00Induction on s. If there exists a vertex of degree...Induction on s. If there exists a vertex of degree <= 2, we are done: removing such a vertex leads to s-1 vertices and at least 2(s-1) edges, and induction does it. Otherwise, the min degree is >= 3, and if we grow a tree starting at an arbitrary vertex, each node should lead to at least two yet-unexplored children, so we will get a cycle within depth log s -- so, cycle length <= 2 * depth <= 2 log s. Was this your proof? --aravindAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20045908467863468422008-11-17T13:41:00.000-06:002008-11-17T13:41:00.000-06:00This is related to the problem of the "Moore bound...This is related to the problem of the "Moore bound". The particular result stated here <I>follows</I> from a paper of Alon+Hoory+Linial: (I'm definitely not saying that's the easiest proof.)<BR/>http://www.math.tau.ac.il/~nogaa/PDFS/ahl1.pdf<BR/><BR/>See, for example, page 10 of Diestel's book "Graph Theory", available on Google Books.Anonymousnoreply@blogger.com