4 ms·

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

by bena 6y ago

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.

Rerarom 6y ago
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"
- daze42 6y ago
  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".
tiagod 6y ago
> 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).
joshuamorton 6y ago
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.
- nickthemagicman 6y ago
  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.
  - _jal 6y ago
    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
  - wongarsu 6y ago
    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.
    - nickthemagicman 6y ago
      Thank you for the clarification I was missing out on that part of it.
- alex_smart 6y ago
  Why even bother adding an edge?
  - verst 6y ago
    Right, even trivial with a 6 vertex path. Or a 6 single vertex forest
  - joshuamorton 6y ago
    Honest answer: because I could think of the term for cycle more quickly than path.
x3n0ph3n3 6y ago
> 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.
adrianN 6y ago
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.
zirkonit 6y ago
> 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.
- bena 6y ago
  That's true. I got caught up in the first half of it. It would be significantly harder to make a ring of six.
  - verst 6y ago
    Even in a ring of six 3 have never met. :)
    - bena 6y ago
      See, even now, knowing I'm not thinking about the negative result, I'm forgetting the negative result.
Out_of_Characte 6y ago
"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.
6gvONxR4sf7o 6y ago
> 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.
deleted 6y ago
[deleted]
ouid 6y ago
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.
- disabled 6y ago
  You may find this interesting: The mystery of the Bermuda Triangle finally ‘solved’?: https://www.ancient-code.com/mysterious-hexagonal-clouds-behind-the-mystery-of-the-bermuda-triangle/ 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.

by bena 6y ago

Rerarom 6y ago

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"

daze42 6y ago
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".

tiagod 6y ago

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

joshuamorton 6y ago

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.

nickthemagicman 6y ago
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.
- _jal 6y ago
  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
- wongarsu 6y ago
  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.
  - nickthemagicman 6y ago
    Thank you for the clarification I was missing out on that part of it.
alex_smart 6y ago
Why even bother adding an edge?
- verst 6y ago
  Right, even trivial with a 6 vertex path. Or a 6 single vertex forest
- joshuamorton 6y ago
  Honest answer: because I could think of the term for cycle more quickly than path.

x3n0ph3n3 6y ago

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

adrianN 6y ago

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.

zirkonit 6y ago

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

bena 6y ago
That's true. I got caught up in the first half of it. It would be significantly harder to make a ring of six.
- verst 6y ago
  Even in a ring of six 3 have never met. :)
  - bena 6y ago
    See, even now, knowing I'm not thinking about the negative result, I'm forgetting the negative result.

Out_of_Characte 6y ago

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

6gvONxR4sf7o 6y ago

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

deleted 6y ago

[deleted]

ouid 6y ago

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.

disabled 6y ago
You may find this interesting: The mystery of the Bermuda Triangle finally ‘solved’?: https://www.ancient-code.com/mysterious-hexagonal-clouds-behind-the-mystery-of-the-bermuda-triangle/ 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.