Comment by bena | Hacker News Reader

Comment by bena | Hacker News Reader

I'm stuck on the beginning example. That in a group of at least six people, there are three people who all know each other.

I think I can violate that one.

I get someone I know from work and someone I know from one of my hobbies that I know don't know each other.

To each of them, I have them get someone from their circle that I've never met. Then I get my wife to get someone from her circle I don't know.

Then you put us all in a room.

I know two people, they know two people, there are two people who only know one other person. And then there's the person my wife invited who knows no one.

There are certain potential violations that can happen. Let's label everyone, I'm A, my guests are B and F, their guests are C and E respectively, my wife's guest is D. Our graph is essentially E-F-A-B-C and D. I know F-B can't happen because I've deliberately chosen people in that manner. And no one other than F and B can connect to A as the instructions were to invite people I don't know.

C-E-F-C, B-C-E-B, D-E-F-D, B-C-D-B, and C-D-E-C are all possible graphs however. But it's also possible that they're not. I'm pretty sure I can engineer it so that it won't be.

But this kind of feels like it violates the spirit of the theory as it's not a natural group, it's a contrived group.

> Among those people, there’s either a group of three who all know each other, or a group of three who have never met.

Or a group of three who have never met. In your example, B, F and D have never met.

That's true. I got caught up in the first half of it.

It would be significantly harder to make a ring of six.

Even in a ring of six 3 have never met. :)

See, even now, knowing I'm not thinking about the negative result, I'm forgetting the negative result.

Ramsey's theorem is a theorem about coloring. You want to color the edges of a complete graph on n vertices with k different colors. The theorem says (among other things) that you can't color the edges of the complete graph with six vertices with just two colors without creating a monochromatic triangle.

The article (and the theorem) says "there’s EITHER a group of three who all know each other, OR a group of three who have never met"

The way it's written this seems like it's exclusive. But it appears that both cases are possible at the same time. Maybe I'm reading the "OR" too much from the colloquial sense instead of the mathematic sense compared to "XOR".

Other people have explained the part of the question that you missed, but in the interest of helping you clarify your own point, if the group of 6 people are all from different continents, and have never met, then you don't have to spend so much time searching for a counterexample.

The actual question as it is posed is perhaps my favorite problem to show school children. So I'll comment on that too, and maybe it will help you.

I draw 6 non collinear points on a white board in a hexagon, and explain to the students that the goal is to place red or green lines between every pair of points in the hexagon so that no red or green triangles whose vertices are all among the 6 points are formed, (here the green lines represent the relation (have met) and the red lines are (haven't met), since we are forcing every line to be colored, this is just the pair of a graph and it's complement). Most students get the idea pretty quickly, and then even get the idea that there are certain subgraphs which make a solution impossible. For instance, if I have any quadrilateral whose edges are colored red red green green, in order, then the diagonal cannot be colored either red or green. Some bright students start to get the sense that if this were possible to do, then it is likely to be possible to do by taking a graph where the condition doesn't hold and replacing one of the legs of an offending triangle.

They start to get the sense that it can't be done, and sometimes one of the students in the class will try to figure out how many graphs they would have to look through in order to prove this by "brute force". The simplest proof is to notice that a vertex with three edges of the same color incident on it is forbidden, but also is necessarily the case for every vertex.

You may find this interesting:

The mystery of the Bermuda Triangle finally ‘solved’?: https://www.ancient-code.com/mysterious-hexagonal-clouds-beh...

> "Meteorologist, Randy Cerveny explained the phenomenon in an interview with the Mirror:"

> "‘These types of hexagonal shapes over the ocean are in essence air bombs. They are formed by what are called microbursts, and they’re blasts of air that come down out of the bottom of a cloud and then hit the ocean and then create waves that can sometimes be massive in size as they start to interact with each other.’"

> "Scientists concluded that massive cloud formations were appearing over the western parts of Bermuda. This caught the attention of Dr. Steve Miller, satellite meteorologist at Colorado State University who told the science channel ‘You don’t typically see straight edges with clouds. Most of the time, clouds are random in their distribution.’"

> "The Mirror believes this enigmatic weather phenomenon is behind the Bermuda Triangle Mystery. To put the mystery of the Bermuda triangle in numbers, on average around four airplanes and twenty ships o missing every year in the Bermuda Triangle."

Interestingly, this shape (as remaining, left-over, air bubbles) occurs when I draw up a medication that I self-infuse (subcutaneous immunoglobulin), because it is so viscous.

Somehow, the red/green edge example makes it easier for me to realize and not drop one of the cases.

> Among those people, there’s *either* a group of three who all know each other, or a group of three who have never met.

In your example, there are three who have never met (your work friend, your hobby friend, and your wife's friend).

> That in a group of at least six people, there are three people who all know each other.

If that's all it was, you could just construct a group of complete strangers as a counterexample. But as others mentioned, you left out the OR part.

"Among those people, there’s either a group of three who all know each other, or a group of three who have never met."

If your wife's friend knows no one, then you can make a group of three in which no one knows each other.

Just pick yourself, and not the person you know from from work or your hobbies. or pick the person from work and not their +1 or yourself. In this manner, in a group of 6. You inescapably have one or the other.

> That in a group of at least six people, there are three people who all know each other.

You left out the "or there are three people who have never met." In your example, C, E, and D have never met each other.

You misread. It's either 3 people who know each other or 3 who have never met. Otherwise it's trivial with a 6-cycle.

Why even bother adding an edge?

Right, even trivial with a 6 vertex path. Or a 6 single vertex forest

Honest answer: because I could think of the term for cycle more quickly than path.

I meant, why bother adding any edge? Just use the empty graph with 6 vertices.

3 people who know each other = T

3 people who don't know each other = F

T || F = T

Isn't that just True by default?

Maybe I'm missing the context.

Let me restate.

9 of the 6 people know each other = T

22 of the 6 people don't know each other = F

T || F = T

If I know Dan but not Dave, then Dan, Dave and I are not 3 people who know each other, but we are not 3 people who don't know each other either.

Thank you for the clarification I was missing out on that part of it.

Reply on news.ycombinator.com