New proof reveals that graphs with no pentagons are fundamentally different
1–10 of 116 posts
Re: New proof reveals that graphs with no pentagons are fundamentally different
#2I'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.
Re: New proof reveals that graphs with no pentagons are fundamentally different
#3I'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…
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"
Re: New proof reveals that graphs with no pentagons are fundamentally different
#4I'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…
> 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).
Re: New proof reveals that graphs with no pentagons are fundamentally different
#5I'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…
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.
Re: New proof reveals that graphs with no pentagons are fundamentally different
#6I'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…
> 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.
Re: New proof reveals that graphs with no pentagons are fundamentally different
#7I'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…
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.
Re: New proof reveals that graphs with no pentagons are fundamentally different
#8I'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…
> 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.
Re: New proof reveals that graphs with no pentagons are fundamentally different
#9can I get an ELI5?
Re: New proof reveals that graphs with no pentagons are fundamentally different
#10I'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…
"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.