Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

New proof reveals that graphs with no pentagons are fundamentally different

quantamagazine.org

Post reply on HN
Print view View original

11–20 of 116 posts

Re: New proof reveals that graphs with no pentagons are fundamentally different

#11

Post by alex_smart »

joshuamorton wrote: post #5
bena wrote: post #2

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…

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?

Re: New proof reveals that graphs with no pentagons are fundamentally different

#12

Post by 6gvONxR4sf7o »

bena wrote: post #2

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…

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

Re: New proof reveals that graphs with no pentagons are fundamentally different

#13

Post by bena »

zirkonit wrote: post #8
bena wrote: post #2

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…

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

Re: New proof reveals that graphs with no pentagons are fundamentally different

#14

Post by verst »

alex_smart wrote: post #11
joshuamorton wrote: post #5

Earlier quoted context omitted.

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

Re: New proof reveals that graphs with no pentagons are fundamentally different

#15

Post by [deleted] »

bena wrote: post #2

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…

[deleted]

Re: New proof reveals that graphs with no pentagons are fundamentally different

#16

Post by verst »

bena wrote: post #13
zirkonit wrote: post #8

Earlier quoted context omitted.

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

Re: New proof reveals that graphs with no pentagons are fundamentally different

#18

Post by nickthemagicman »

joshuamorton wrote: post #5
bena wrote: post #2

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…

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.

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.

Re: New proof reveals that graphs with no pentagons are fundamentally different

#19

Post by bena »

verst wrote: post #16
bena wrote: post #13

Earlier quoted context omitted.

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.

Re: New proof reveals that graphs with no pentagons are fundamentally different

#20

Post by _jal »

nickthemagicman wrote: post #18
joshuamorton wrote: post #5

Earlier quoted context omitted.

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.

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

Post reply on HN