Comments on research!rsc: Mel was Real

I'm afraid my attempt to make the proof accessible...

2008-05-04T13:39:00.000-04:00

I'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.

Corollary: Knowing each other is no different from not knowing each other.

Since every open problem should be solved there yo...

2008-05-03T21:12:00.000-04:00

Since every open problem should be solved there you go:

mn proves that if someone knows 3 others then either a clique or an anti-clique is created, which is correct.

So the corollary is that everybody knows at most 2 others. If the whole group is denoted by {a,b,c,d,e,f} and someone, e.g. a, knows 2 others, say b and c, then there is someone in the {d,e,f} that b and c do not know, e.g. d. If {a,b,c} is not a clique then {b,c,d} is an anti-clique.

If anyone knows exactly 1 person, then a anti-clique is created.QED!

Excuse me for my geek-ness, but I like such things. Nice blog rsc. I'll be around

mn: that is a very nice proof indeed!

2008-05-03T09:24:00.000-04:00

mn: that is a very nice proof indeed!

Funny story. Just wondering... Do you feel like a ...

2008-05-02T21:34:00.000-04:00

Funny story.

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.

Actually, you only proved that you have at least t...

2008-05-02T18:28:00.000-04:00

Actually, 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:

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.

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.

Hmm I think you could enumerate the cases for that...

2008-05-01T23:38:00.000-04:00

Hmm 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:
- 0, 1 edge => an anti-clique exists
- 2,3 edges: if no common vertex => an anti-clique exist, otherwise a clique exist
- 4 or more edges => there has two be a common vertex (pigeon-hole principle here) => a clique exist

Just to be clear, James wasn't at all negative abo...

2008-04-30T13:09:00.000-04:00

Just 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.

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.

Theory graders seem to have a thing about brute fo...

2008-04-30T12:13:00.000-04:00

Theory 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.