Hacker News Reader

Comment by bongodongobob | Hacker News Reader

Because it's saying "you have 6 blocks, they can be either green or blue. No matter what colors they are, you'll always have either 3 blue or 3 green."

View on HN

Just so you know: you've completely misunderstood the statement.

Let me see if I can clear up your misunderstanding: it is totally possible to have 5 people without having a group of 3 which are all friends nor a group of 3 none of which are friends. Draw a fully connected pentagon with all the outer edges one color and the inner edges another color. There is no triangle that is all the same color.

But with 6 nodes you must have a triangle that is all the same color. It is the edges that are colored, not the nodes.

You misunderstood the problem. That's not what it's saying at all.

How isn't it? There's no way to have 3 connected friends and 4 unconnected friends.

You can have all 6 connected and still be in either category.

For example, 6 friends in a loop can be divided into even and odd trios, where each trio has no direct friend connections within it.

But six people in two separate triangles fall into the other category, with two trios of mutual friends.

Notice how both of these cases give each person 2 friends. It's not nearly as simple as assigning everyone a color at the start.

Another thing to think about: If you have a triangle of 3, and a line of 3, then you can find 3 mutual friends and three mutual non-friends. How would you use colors to differentiate this situation from the two-triangles situation?

No, that's what I'm saying. You're either a member of the 3-group or you're not. It clearly requires 3 members, so...

It's proving the 3 nodes with no direct connections to each other that is the complicated part.

It's not "you have a group of 3 or you don't".

You can have all six people tangled up in lots of different combinations, so how do you prove there's a way to pick three that only connect indirectly?

You could have one green and five blue

Uh, exactly. You've got 3 blue in that 5.

Sorry I was thinking too fast

I think it’s more accurate as: at least 3 which are blue or at least 3 which aren’t blue. Which is obvious even if perhaps the statement at the top of the thread is not.

You have not understood the statement.

In that case, would you mind writing a more enlightening comment?

It's probably most clearly stated in the original post, but the point is you would either be able to find three people who are all friends with the other two, or you would be able to find three friends who are not friends with any of the others. The non-obviousness is due to the fact that someone may have only one friend, or someone may have two friends but those two would not be friends with each other, so I wouldn't call it blindingly obvious that there would always be a subset with one of these properties (I think the main intuition that is useful is that if you have a sparsely connected graph of friends, it's easy to find a group that aren't friends at all, and if you have a densely connected graph then you can find a group that are mutual friends. The theorem is then proving that there's no middle ground: it's either dense enough a mutual group must exist or sparse enough a non-friend group must exist.)

In your version, the color of a vertex is independent of other vertices. The real problem is about entirely about connections to other vertices. The latter cannot be reduced to the former.

Does this formulation work?

You have 6 wooden blocks, each can be 1 of 6 colors. There will always be either (A) 3 blocks of the same color, or (B) 3 blocks of different colors.

Iterating through all possibilities:

6 of 1 color - case A

5 of 1 color, 1 of another - case A

4 of 1 color, 2 of another - case A

4 of 1 color, 1 of another, 1 of yet another - case A and B

3 of 1 color, 3 of another - case A

3 of 1 color, 2 of another, 1 of yet another - case A and B

3 of 1 color, 1 of another, 1 of yet another, 1 of another another - case A and B

2 of 1 color, 2 of another, 2 of yet another - case B

2 of 1 color, 2 of another, 1 of yet another, 1 of another another - case B

2 of 1 color, 1 of another, 1 of yet another, 1 of another another, 1 of another another another - case B

all colors different - case B

Your formulation is not equivalent. The actual Ramsey theory formulation is something more like...you need to color, either red or blue, all of the edges of a fully connected graph of 6 elements (there are 15 such edges). No matter which coloring you choose (there are 2^15 of these), there will always be a "triangle" between three nodes where the entire triangle is either fully red, or fully blue. If you were to instead restrict yourself to a graph with 5 elements instead of 6, it's possible[1] to color the edges so there's no triangle where all the elements are the same.

As an exercise, try repeating your same argument for 5 colors/blocks, and note that it still works, when it shouldn't.

[1] - https://commons.wikimedia.org/wiki/File:RamseyTheory_K5_no_m...

Reply on news.ycombinator.com