Live data from Hacker News

New proof reveals that graphs with no pentagons are fundamentally different

quantamagazine.org

101–110 of 116 posts

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

#101
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…

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…

Good observation and I think relevant to show the difference between how maths is taught and how art is taught.

Imagine if you started to learn art by doing shading drills, or practising how to use a paint brush by making the same stroke over and over again, but never actually painting a picture.

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

#102
post #35

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…

aaand I just realized I’m only 3

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

#104
post #45
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…

Somehow, the red/green edge example makes it easier for me to realize and not drop one of the cases.

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

#106
post #99

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

I can’t get in your head to know what you’re thinking so maybe it is obvious to you, but just in case you don’t fully understand: it may not be obvious that its impossible to have a configuration where in the 20 possible groups of 3, someone always knows someone else but not everyone knows everyone? The theorem isn’t really saying “it’s A or not A”. It’s saying: “it has to be A or B and not anything else”.

If you pair everyone off, either all three groups are disjoint, or some of the groups are connected.

If you don't pair people, you end up with 2 completely disconnected people and also at least one more person that's not connected to either

Obviously if you make a group bigger than a pair, you also end up with 3 connected people

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

#107
post #28
post #24

I'm impressed by how clear the article is for a layman. I only know the very basics of graph theory and Ramsay theory and I understood the topic perfectly. This is in comparison to the paper [1] which at a glance seems terse and difficult to understand. If anyone likes Ramsay theory and these kind of articles, I recommend Erdős' biography "The Man Who Loved Only Numbers". [1] https://arxiv.org/abs/2102.04994

Quanta Magazine does an excellent job with balancing accessible writing and advanced topics. It's just enough to get someone interested in the problem and the basic ideas to start thinking about it.

I wonder who it's written for? I feel like I understand all the articles, which is worrying because how would I know if I'm right.

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

#109
post #28

Earlier quoted context omitted.

Quanta Magazine does an excellent job with balancing accessible writing and advanced topics. It's just enough to get someone interested in the problem and the basic ideas to start thinking about it.

I wonder who it's written for? I feel like I understand all the articles, which is worrying because how would I know if I'm right.

The usual Gell-Mann way - when they write an article about a topic you know very well, you see whether you find it "mildly annoying" (because there are always small inaccuracies or papering-overs that seem a big deal to us), or "hilariously bad", or "so outrageous the writer ought to be fired". The quality of the other articles you aren't qualified to judge can then be assumed to be in a cloud around where you judged this one to be.

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

#110

Earlier quoted context omitted.

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…

As a person who briefly pursued a degree in a traditional engineering discipline before finding my way back to the arts (music) and then eventually into a software career, I think the difference - at least for me - is that with the arts I've never gotten the impression that the fundamentals stop being interesting if they're still applied well. To phrase it another way: practicing scales can be boring. But playing a w…

As a mathematician, I would claim that math at its best is exactly about riffing and jamming on shared fundamentals and adding your own insights. But it is often misunderstood what these fundamentals are: not the proofs or the formulas, but the elements of logical reasoning that make it possible to say with absolute certainty that given some conditions, some statement must be absolutely true.

A riff on a proof in geometry isn't changing a few of the letters around to see if still works - it might instead be about changing the assumptions. In plane geometry, the angles of a triangle sum to 180 degrees. But what if we are not in the plane, but on the surface of a sphere, such as the earth? Does a triangle connecting the north pole to two points on the equator still have the sum 180 degrees? If not, can we prove something else about it? In the context of the original article, it might be something like "Can we use any parts of our proof about pentagons (5-cycles) for some other shapes? What about hexagons (6-cycles)? Or is there even any insight we can generalize so that it becomes a statement about cycles of any length?"

Sadly, this is way too seldom the way math is taught. I didn't enjoy the endless calculations of long division in grade school, or the memorization of different tricks for solving trigonometric integrals in college, either.

For a famous mathematician quote, how about Paul Erdös concept of "a proof from the Book" - said about math proofs that are so perfect and clear that they must be in God's celestial collection. Often, there is more than one way to prove something true - checking every example by brute force would be the most extreme - but sometimes you can discover an elegant argument that just convinces everyone who reads it that it simply must be true. That could also be thought of as riffing on a proof: Ok, you convinced me that this is true, after many boring pages of calculations - can I find a simpler way to convince myself of the same thing, and improve both our understandings?" Quanta magazine had a nice article about this as well: https://www.quantamagazine.org/gunter-ziegler-and-martin-aig...

Post reply on HN