New proof reveals that graphs with no pentagons are fundamentally different • Hacker News Board

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

#71

Post by CrazyStat » Mon, Apr 26, 2021, 8:00 PM UTC

btilly wrote: post #57

Cerium wrote: post #50

Earlier quoted context omitted.

It would require an advance in theory. When I took a graph theory course it fascinated me how the Ramsey theory problem goes from paper and pencil complexity to beyond computing power in two steps (R(3,3) = 6, R(4,4) = 18, R(5,5)=(43..48?)). I once spent some time calculating the effort (but don't have the results handy), a rough number for a naive approach to exhaustively searching the problem space would involve so…

It is worse than that. Here is the calculation. The number of graphs of size n is 2^(n choose 2). (There are n choose 2 pairs of points, each of which could be or not be an edge.) If the answer is 43, that's 2^903 which is roughly 6.762 * 10^271. If the answer is 48, that's 2^1128 which is roughly 3.646 x 10^339. Naive plus better computers is not enough to tackle this problem.

>The number of graphs of size n is 2^(n choose 2).

This is overcounting by many orders of magnitude. For example, there's only one graph with one edge, not (n choose 2). For n = 43 you're overcounting these graphs by a factor of 903.

Similarly there are only two graphs with two edges (either the two edges are connected or not), not ((n choose 2) choose 2). For n = 43 you're overcounting these graphs by a factor of ~200k.

For graphs with three edges you can have (1) a triangle, (2) three edges connected end to end forming a single path, (3) three connected edges forming a star, (4) two connected edges and one single, or (5) three unconnected edges. Compared to your count of ((n choose 2) choose 3), you're overcounting by a factor of about 24 million for n=43.

The total (over)count is going to be dominated by graphs with approximately (n choose 2)/2 edges, which intuitively is where I also expect the overcounting factor to peak.

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

#72

Post by drdeca » Mon, Apr 26, 2021, 8:07 PM UTC

> the pentagon (or really any five-sided polygon)

An odd line.

Surprising given the quality of the rest of the article.

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

#73

Post by lainga » Mon, Apr 26, 2021, 8:13 PM UTC

drdeca wrote: post #72

> the pentagon (or really any five-sided polygon) An odd line. Surprising given the quality of the rest of the article.

maybe it's a regularising "the", like "the Moon" vs. "a moon"... "the" regular pentagon, vs., etc.

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

#74

Post by concreteblock » Mon, Apr 26, 2021, 8:14 PM UTC

concreteblock wrote: post #51

GordonS wrote: post #46

Earlier quoted context omitted.

A bit of an aside, but this was always my biggest bugbear when learning maths way back when I was in school - we were never given any practical reasons of why any of it was useful. Even if you explicitly asked the maths teacher "what's it for", they could never give a useful response - it often seemed like they'd never considered this themselves. Around 13-14 years old, I got interested in building mods for Quake. Wh…

Big reason is that many high school math teachers don't really understand math well enough for the job.

To clarify, since I can't edit: This is coming from my experience as someone who has taught math to teachers getting their master's degree. It sounds mean but I wanted to emphasize that the state of early math education is not just due to poorly designed curriculum, but because there is little incentive for mathematically competent people to teach children. (Imo, of course).

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

#75

Post by thaumasiotes » Mon, Apr 26, 2021, 8:16 PM UTC

lainga wrote: post #73

drdeca wrote: post #72

> the pentagon (or really any five-sided polygon) An odd line. Surprising given the quality of the rest of the article.

maybe it's a regularising "the", like "the Moon" vs. "a moon"... "the" regular pentagon, vs., etc.

The use of "the" isn't the weird part. The weird part is that the article attempts to draw a contrast between "pentagons" and "five-sided polygons", which are exactly the same thing.

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

#76

Post by waluigi » Mon, Apr 26, 2021, 8:19 PM UTC

thaumasiotes wrote: post #75

lainga wrote: post #73

Earlier quoted context omitted.

maybe it's a regularising "the", like "the Moon" vs. "a moon"... "the" regular pentagon, vs., etc.

The use of "the" isn't the weird part. The weird part is that the article attempts to draw a contrast between "pentagons" and "five-sided polygons", which are exactly the same thing.

I think what the poster above is saying is that by saying "the pentagon" the author is referring to the (unique) 5 sided regular polygon, as opposed to some random, potentially non-regular 5 sided polygon.

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

#77

Post by frogpelt » Mon, Apr 26, 2021, 8:25 PM UTC

thaumasiotes wrote: post #75

lainga wrote: post #73

Earlier quoted context omitted.

maybe it's a regularising "the", like "the Moon" vs. "a moon"... "the" regular pentagon, vs., etc.

The use of "the" isn't the weird part. The weird part is that the article attempts to draw a contrast between "pentagons" and "five-sided polygons", which are exactly the same thing.

Pentagons are 5-sided polygons where all the sides are equal. Not all 5-sided polygons are pentagons. What am I missing?

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

#78

Post by thaumasiotes » Mon, Apr 26, 2021, 8:25 PM UTC

waluigi wrote: post #76

thaumasiotes wrote: post #75

Earlier quoted context omitted.

The use of "the" isn't the weird part. The weird part is that the article attempts to draw a contrast between "pentagons" and "five-sided polygons", which are exactly the same thing.

I think what the poster above is saying is that by saying "the pentagon" the author is referring to the (unique) 5 sided regular polygon, as opposed to some random, potentially non-regular 5 sided polygon.

That would not stop it from being a bizarre error in an otherwise decent article. There is no such use.

I interpreted it in the same way as e.g. "the cow has four stomachs".

This is a question about graph theory anyway; there are no side lengths or interior angles.

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

#79

Post by MadcapJake » Mon, Apr 26, 2021, 8:38 PM UTC

frogpelt wrote: post #77

thaumasiotes wrote: post #75

Earlier quoted context omitted.

The use of "the" isn't the weird part. The weird part is that the article attempts to draw a contrast between "pentagons" and "five-sided polygons", which are exactly the same thing.

Pentagons are 5-sided polygons where all the sides are equal. Not all 5-sided polygons are pentagons. What am I missing?

What you're describing is called a regular pentagon.

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

#80

Post by karaterobot » Mon, Apr 26, 2021, 8:38 PM UTC

>... if the room has at least six people, you can say something about them with absolute mathematical certainty... [that it contains] either a group of three who all know each other, or a group of three who have never met.

Maybe I'm incredibly dense, but this seems tautologically true, and not worth mentioning. Could somebody kindly explain what I'm missing?