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

51–60 of 116 posts

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

#51

Post by concreteblock »

GordonS wrote: post #46
WaitWaitWha wrote: post #17

It would help if the article included at least one real world application in layman's terms.

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.

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

#52

Post by mjcohen »

mFixman wrote: post #25
WaitWaitWha wrote: post #17

It would help if the article included at least one real world application in layman's terms.

Because you are finding the secrets of the Universe? Because math is fun? Not all work has to have a real world application ($$$). It would help if the you included at least one real world application of writing your comment.

A real world application is getting someone to respond with a real world application that would help you make money.

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

#55

Post by Akronymus »

GordonS wrote: post #46
WaitWaitWha wrote: post #17

It would help if the article included at least one real world application in layman's terms.

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…

For me, learning a subject in school is much harder than learning it "in the real world" precisely because I often lack the connection to it being practical or it otherwise just being taught as what instead of why. For me the connection of why it is like that makes me actually grok it, rather than forgetting it after 5 minutes.

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

#56

Post by ball_of_lint »

mFixman wrote: post #35
luxuryballs wrote: post #9

can I get an ELI5?

The Erdős–Hajnal conjecture says that for any graph `H`, then every graph in the set of graphs `F_H` that does not contain `H` as an induced subgraph will either have a polynomial amount of cliques or a polymomial amount of independent sets. The growth rate of the exponent depends on the size of each graph in `F_H` and on some properties `H`. Like with most simple questions in Ramsay theory no proof or contradiction…

I think I'm misunderstanding or you left out an important condition.

For your example where H forms a loop, I imagine an element of F_H which is a larger loop. Then it could be arbitrarily large, have no cliques above size 2, a linear number of cliques of size 2, and have only one independent set.

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

#57

Post by btilly »

Cerium wrote: post #50
voldacar wrote: post #30

Question for people knowledgable about Ramsey theory - with current computing tech, will we ever be able to find the exact value of R(5,5) within our lifetimes? I've read the famous Erdos quote about R(5,5) vs R(6,6) and he seemed to think that it was at least theoretically possible if the whole human race had to find it quickly or face destruction.

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.

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

#58

Post by boomboomsubban »

GordonS wrote: post #46
WaitWaitWha wrote: post #17

It would help if the article included at least one real world application in layman's terms.

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…

This sentiment is incredibly common, and it's strange that you then get to calculus where the real world applications are such an integral part of the subject.

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

#59

Post by visarga »

jerf wrote: post #44
visarga wrote: post #23

Earlier quoted context omitted.

and an application ... what can I use it for?

Ramsey theory in a nutshell is about studying what must be true about graphs as they get large in certain ways, because the very size of the graph makes it impossible for the things to be false any longer. My impression is that it tends to be more useful for putting bounds on how good a practical technique can be rather than directly producing said direct techniques. It's not quite the same as complexity theory in co…

Thanks, great answer

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

#60

Post by visarga »

dpatterbee wrote: post #29
visarga wrote: post #23

Earlier quoted context omitted.

and an application ... what can I use it for?

I can't possibly imagine why you would want an application for recently developed mathematics. I would have thought that by now mathematics would have proven its worth enough to not have to justify itself.

I assumed an implied AI application on graphs.
Post reply on HN