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

61–70 of 116 posts

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

#61

Post by Dagonfly »

ball_of_lint wrote: post #56
mFixman wrote: post #35

Earlier quoted context omitted.

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.

I'm not an expert, but I think you are confused about what 'independent set' means. It's basically 'no vertex pair v,w in the set has a edge (v,w)'

So in your loop example, you can take every other vertex in the loop and those form an independent set (of size n/2 ish). And n/2 is in Ω(n).

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

#62

Post by bordercases »

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…

There is not one way any piece of mathematics is useful, and we don't always know ahead of time what kind of mathematics is useful or not.

That's why it's (a) important to know how mathematics can be built from concrete instances, like you did with your Quake Bot, and (b) that it takes a lot of practice with mathematics to know how mathematical modeling is generally done, so that you can see how incremental advances in higher mathematics might lead to breakthroughs in applied mathematics in the future.

Otherwise mathematics fulfills an aesthetic sense for beauty and elegance in one's own thinking that most people's minds don't seem to support by default. There's nothing wrong with that, but it's just as valid an attitude to the subject as presuming everything should be motivated by applications at first. To those people who enjoy mathematics for its own sake, it's a form of play which might organize something important in the future, that you otherwise would have missed because you're too busy applying some other form of mathematics.

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

#63

Post by disabled »

ouid wrote: post #45
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…

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…

You may find this interesting:

The mystery of the Bermuda Triangle finally ‘solved’?: 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.

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

#64

Post by klyrs »

WaitWaitWha wrote: post #17

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

I just did a search for "real-world applications of Ramsey theory" and this was the closest I got. Sorry.

http://www.cs.umd.edu/~gasarch/BLOGPAPERS/ramseykings.pdf

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

#65

Post by nickthemagicman »

wongarsu wrote: post #34
nickthemagicman wrote: post #18

Earlier quoted context omitted.

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.

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.

Thank you for the clarification I was missing out on that part of it.

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

#66

Post by elliekelly »

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 comment resonates with me so much. I remember learning how to program, as an adult, and having an epiphany about all those times my teachers wrote f(x) and then proceeded to write some hodgepodge of numbers and letters. No one had ever explained why I would ever need some function for x to spit out something else and so I was sort of lost from the very beginning when it came to any kind of high level math. Ditto for sets and pairs. Basically all of my math education was a complete waste until I learned a bit of computer programming and could play around with implementing the abstract concepts and relate those concepts to practical uses. Then suddenly it all made so much more sense!

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

#68

Post by abdullahkhalids »

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…

As a teacher, I believe applications must be discussed - I am a physicist after all.

But I remember my peers asking for applications from math teachers when we were in school, but I never saw them ask the same from art teachers. Somehow, everyone understood that drawing and coloring were just for pleasure and stroking our aesthetic sensibilities, and an application was not needed. But people rarely think of math the same way. Yet, it's all pattern recognition and creation.

Post reply on HN