tag:blogger.com,1999:blog-8082954141980125536.post88388799571459136..comments2012-01-17T19:08:38.013-08:00rschttp://www.blogger.com/profile/09449562785422464948noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-8082954141980125536.post-62921729621185980272011-08-02T20:08:06.638-07:002011-08-02T20:08:06.638-07:00From Turan&#39;s Theorem, a triangle-free graph (meaning no 3-member cliques) with the maximum number of edges is a complete bipartite graph in which the number of vertices on each side are as equal as possible.<br /><br />In this case, we have 6 people, so we have a bipartite graph with 3 people on each side. This means that even with the maximum number of edges in the graph without a clique of three people, we still have two anti-cliques of three people.Robert Bloomquisthttp://www.blogger.com/profile/14995249833622345826noreply@blogger.comtag:blogger.com,1999:blog-8082954141980125536.post-62850637025978058962010-07-07T09:01:40.932-07:002010-07-07T09:01:40.932-07:00sorry for necroposting, but I would like to see If this &#39;solution&#39; of mine would be a solution too. I thought of it in half an hour and I&#39;m currently 26 hours without sleep, so I wouldn&#39;t wonder if not, but I want to know what goes through for a proof and what doesn&#39;t.<br /><br />I&#39;ll just start with the 6 vertices. Right now, there is only anti-cliques. I will now, one after another, add edges such that no clique is formed. Once a clique is formed, I have lost anyway.<br />My first 5 edges are able to eliminate 4 anti-cliques each.<br />6 and 7 each eliminate three further anti-cliques.<br />In this state, there is still at least one anti-clique.<br />Adding any other edge will now create a clique and hence loose.<br />Since no further anti-cliques can be eliminated without creating a clique, it is not possible to win the game.<br /><br />I hope someone reads this and gives me a comment = )<br /><br />Best wishes, DavidJoneshttp://www.blogger.com/profile/13193072767938982221noreply@blogger.comtag:blogger.com,1999:blog-8082954141980125536.post-61130671468533230722008-05-04T10:39:00.000-07:002008-05-04T10:39:00.000-07:00I'm afraid my attempt to make the proof accessible backfired badly. An equivalent formulation of the problem would be: Every complete graph with two edge colours has a unicoloured three-cycle. (In our case, draw a blue edge between two persons knowing each other and a red one between two not knowing each other.) Then the proof is as follows: Pick one vertex. Then there are three others connected to the first with edges of the same colour. If between two of those is an edge in the same colour these two form a three-cycle with the first one. Otherwise the three new ones form a three-cycle.<BR/><BR/>Corollary: Knowing each other is no different from not knowing each other.mnhttp://www.blogger.com/profile/14714143877057723159noreply@blogger.comtag:blogger.com,1999:blog-8082954141980125536.post-6707445087027933832008-05-04T10:17:00.000-07:002008-05-04T10:17:00.000-07:00This comment has been removed by the author.mnhttp://www.blogger.com/profile/14714143877057723159noreply@blogger.comtag:blogger.com,1999:blog-8082954141980125536.post-70791276979234746772008-05-03T18:12:00.000-07:002008-05-03T18:12:00.000-07:00Since every open problem should be solved there you go:<BR/><BR/><I>mn</I> proves that if someone knows 3 others then either a clique or an anti-clique is created, which is correct.<BR/><BR/>So the <B>corollary</B> is that everybody knows <B>at most</B> 2 others. If the whole group is denoted by <B>{a,b,c,d,e,f}</B> and someone, e.g. <B>a</B>, knows 2 others, say <B>b</B> and <B>c</B>, then there is someone in the <B>{d,e,f}</B> that <B>b</B> and <B>c</B> do not know, e.g. <B>d</B>. If <B>{a,b,c}</B> is not a clique then <B>{b,c,d}</B> is an anti-clique.<BR/><BR/>If anyone knows exactly 1 person, then a anti-clique is created.QED!<BR/><BR/>Excuse me for my geek-ness, but I like such things. Nice blog <B>rsc</B>. I'll be aroundpanefskyhttp://www.blogger.com/profile/00875709636921240567noreply@blogger.comtag:blogger.com,1999:blog-8082954141980125536.post-61944059974772026602008-05-03T06:24:00.000-07:002008-05-03T06:24:00.000-07:00mn: that is a very nice proof indeed!Stephan202http://www.blogger.com/profile/03746679755202178161noreply@blogger.comtag:blogger.com,1999:blog-8082954141980125536.post-78759073795966343312008-05-02T18:34:00.000-07:002008-05-02T18:34:00.000-07:00Funny story. <BR/><BR/>Just wondering... Do you feel like a dumbass after a brute force solution to the problem cos I do. I am taking an algorithms class in college and my grader (like yours) is a nice guy. He probably would give me full credit for a brute force solution, too. But I feel shitty after writing brute force solutions.ABcdeFUhttp://www.blogger.com/profile/15949923138486620207noreply@blogger.comtag:blogger.com,1999:blog-8082954141980125536.post-57716464202960250192008-05-02T15:28:00.000-07:002008-05-02T15:28:00.000-07:00Actually, you only proved that you have at least three connected/disconnected people, a much easier condition to ask for. I'm a little scared that a correct prove immediately sprang to my mind. (From memory, though. Little originality here on my part.) But since a wrong one's already there, I might as well post it:<BR/><BR/>Choose one person. That person either knows three other persons or dosn't know three others (pigeonhole principle.) For symmetry reasons we can assume he knows three others. If two among those know each other, too, we have found a clique, else an anti-clique.<BR/><BR/>After all those years I'm still amazed by the simplicity and elegance of the proof. (And I could resist to use graph theory nomenclature.) But that ``challenge'' is also a curious one: Basically it's the theory of Ramsey-numbers backwards.mnhttp://www.blogger.com/profile/14714143877057723159noreply@blogger.comtag:blogger.com,1999:blog-8082954141980125536.post-68358916094587527412008-05-01T20:38:00.000-07:002008-05-01T20:38:00.000-07:00Hmm I think you could enumerate the cases for that problem: consider a graph with 6 ppl being vertexes, an edge represent two ppl knowing each other. Counting the edges:<BR/>- 0, 1 edge => an anti-clique exists<BR/>- 2,3 edges: if no common vertex => an anti-clique exist, otherwise a clique exist<BR/>- 4 or more edges => there has two be a common vertex (pigeon-hole principle here) => a clique existChickhttp://www.blogger.com/profile/13784541025357015160noreply@blogger.comtag:blogger.com,1999:blog-8082954141980125536.post-34605226088248934102008-04-30T10:09:00.000-07:002008-04-30T10:09:00.000-07:00Just to be clear, James wasn't at all negative about it, and I did get full credit for the answer. I just thought it was a funny, insightful comment. Unfortunately, any student at that point in the course wouldn't appreciate it. I only noticed it looking back through my problem sets a couple years later.<BR/><BR/>As a former grader myself in many contexts, I understand the "but that's not what we wanted you to do" knee-jerk reaction, but it's the problem-writer's job to make sure that can't happen. If the gradee finds a better/different solution, more power to them.rschttp://www.blogger.com/profile/09576271159839887762noreply@blogger.comtag:blogger.com,1999:blog-8082954141980125536.post-48117117243178465952008-04-30T09:13:00.000-07:002008-04-30T09:13:00.000-07:00Theory graders seem to have a thing about brute force. In some UCB grad theory class I was marked down for a correct proof because I enumerated the whole set of cases, instead of being fancy and avoiding brute force. There were, IIRC, *4* cases.stevehttp://www.blogger.com/profile/13405395955183065842noreply@blogger.com