9 ms·
New proof reveals that graphs with no pentagons are fundamentally different
- jefurii 6y agoI bet that Maria Chudnovsky in the article is related to the Chudnovsky brothers (Gregory and David) who were the inspiration of the 1998 mathematical/psychological movie Pi by Darren Aronofsky. See also: https://www.newyorker.com/magazine/1992/03/02/the-mountains-of-pi https://www.newyorker.com/magazine/1992/03/02/the-mountains-...
- WaitWaitWha 6y agoIt would help if the article included at least one real world application in layman's terms.
- mFixman 6y agoBecause 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.
- boomboomsubban 6y agoEven when math does have profound real world applications they aren't always immediately apparent. Think of how many millennia work was done on primes before they became a huge part of cryptography, though they did have some other uses along the way.
- mjcohen 6y agoA real world application is getting someone to respond with a real world application that would help you make money.
- GordonS 6y agoA 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. When I decided to create a bot, I finally understood at least how trigonometry was useful. I won the annual mathematics prize at school that year, and I'm sure it was only because real-world use had gotten me interested.
- concreteblock 6y agoBig reason is that many high school math teachers don't really understand math well enough for the job.
- concreteblock 6y agoTo 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).
- chadcmulligan 6y agoThe other problem in my experience (as a parent and math nerd) is that the whole math teaching area is full of people who don't know math, so coming in and having a math person teach math means you have a huge number of arguments you'd have to have. The only way I know of is to just get after school tuition and ignore the school. This is difficult though - why do I have to do maths after school? no one else does.
- Akronymus 6y agoFor 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.
- _rpd 6y agoThis finding expands our knowledge of graphs. The classic application of graphs is logistics, but there are many, many more ... https://en.wikipedia.org/wiki/Graph_theory#Applications https://en.wikipedia.org/wiki/Graph_theory#Applications
- klyrs 6y agoI 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 http://www.cs.umd.edu/~gasarch/BLOGPAPERS/ramseykings.pdf
- einpoklum 6y agoA research grant application maybe? :-P
- bena 6y agoI'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 us all in a room. I know two people, they know two people, there are two people who only know one other person. And then there's the person my wife invited who knows no one. There are certain potential violations that can happen. Let's label everyone, I'm A, my guests are B and F, their guests are C and E respectively, my wife's guest is D. Our graph is essentially E-F-A-B-C and D. I know F-B can't happen because I've deliberately chosen people in that manner. And no one other than F and B can connect to A as the instructions were to invite people I don't know. C-E-F-C, B-C-E-B, D-E-F-D, B-C-D-B, and C-D-E-C are all possible graphs however. But it's also possible that they're not. I'm pretty sure I can engineer it so that it won't be. But this kind of feels like it violates the spirit of the theory as it's not a natural group, it's a contrived group.
- Rerarom 6y agoThe article (and the theorem) says "there’s EITHER a group of three who all know each other, OR a group of three who have never met"
- daze42 6y agoThe way it's written this seems like it's exclusive. But it appears that both cases are possible at the same time. Maybe I'm reading the "OR" too much from the colloquial sense instead of the mathematic sense compared to "XOR".
- tiagod 6y ago> Among those people, there’s *either* a group of three who all know each other, or a group of three who have never met. In your example, there are three who have never met (your work friend, your hobby friend, and your wife's friend).
- joshuamorton 6y ago
- luxuryballs 6y agocan I get an ELI5?
- ComodoHacker 6y agoI guess that's already it. :)
- system2 6y agoToday's 5 year olds are all mathematicians anyway.
- visarga 6y agoand an application ... what can I use it for?
- Mountain_Skies 6y agoPerhaps not much now but a use for them might come along and it will be good that this will be there ready to fill the need. It's my understanding that quaternions were mostly a curiosity when first described in the mid 1800s but now are used extensively in computing. From wikipedia "quaternions are used in computer graphics, computer vision, robotics, control theory, signal processing, attitude control, physics, bioinformatics, molecular dynamics, computer simulations, and orbital mechanics." When Sir William Rowan Hamilton first described them, he had no concept of most of the above, much less that quaternions would be important for them. Good for us that he still pushed forward with them.
- 101008 6y agoFirst paragraph of the article says something interesting that can be useful at parties :)
- dpatterbee 6y agoI 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.
- jeffrallen 6y agoA world without the Pentagon would be fundamentally different too. More peaceful...
- mFixman 6y agoI'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 https://arxiv.org/abs/2102.04994
- strmpnk 6y agoQuanta 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.
- astrange 6y agoI 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.
- sundarurfriend 6y agoThe 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.
- astrange 6y agoI have the opposite problem here. The CS articles seem fine, but I don't know who would be interested in Quanta's articles but only capable of understanding things at their writing level. It doesn't seem like they should have an audience.
- voldacar 6y agoQuestion 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.
- willowfine 6y agoI did some work in Ramsey theory 20 years ago (improved the upper boundaries for R(3,12) and R(3,15) by one digit each [1]) and I agree with Erdös: we could do it, if there was a compelling reason to devote a lot of effort to it. As others have said, brute force is just plain impossible. But we can limit the search space significantly by proving sub-results about the structures of the possible graphs. Somewhat trivial example to give the flavor: let's state the problem as "find the smallest number of vertices needed such that any graph must have either a 5-connected component (a "pentagram") or 5 independent vertices". We know that the number is at least 43. So if we are looking for a counterexample, a graph on 43 vertices that does not have either of these two subgraphs, what can we say about the possible number of edges that each vertex must have? (the degree, for graph theorists). We can immediately say that if we have 5 or more vertices with no edges (degree 0) then we have our independent set already, so any counterexample can have at most 4 vertices of degree 0. By the way, my favorite Explain-like-I'm-5 version of Ramsey's theorem is "Total disorder is impossible": If a structure is large enough, there must be some substructure that is ordered. [1] https://www2.math.su.se/ramseytheory/sciramseyams.pdf https://www2.math.su.se/ramseytheory/sciramseyams.pdf
- thanksforfish 6y agoThat quote is: "Suppose aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack." https://blogs.scientificamerican.com/roots-of-unity/moores-law-and-ramsey-numbers/ https://blogs.scientificamerican.com/roots-of-unity/moores-l...
- barbiturique 6y agoDoes that mean something for our usage of graph? Is there folks out-there who would benefit from being able to know stuff about a graph just by knowing it has pentagon in it? ( or vice versa ) The article is enjoyable to read. I smiled at "well, we can't do a general proof at the moment, and it might be a lot of work to do so still. But, if we put a hat on the pentagon, we can prove it"
- deleted 6y ago[deleted]
- TheMagicHorsey 6y agoWhat is a good book to read to learn about graph theory?
- kruuuder 6y agoIf you're looking for a book that shows you the joy of graph theory, try Reinhard Diestel's book. It's both deep and playful.
- paulyy_y 6y agoArachnophobes beware
- drdeca 6y ago> the pentagon (or really any five-sided polygon) An odd line. Surprising given the quality of the rest of the article.
- lainga 6y agomaybe it's a regularising "the", like "the Moon" vs. "a moon"... "the" regular pentagon, vs., etc.
- thaumasiotes 6y agoThe 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.
- waluigi 6y agoI 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.
- thaumasiotes 6y agoThat 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.
- frogpelt 6y agoPentagons are 5-sided polygons where all the sides are equal. Not all 5-sided polygons are pentagons. What am I missing?
- MadcapJake 6y agoWhat you're describing is called a regular pentagon.
- karaterobot 6y ago>... 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?
- hoseja 6y agoOne could know the Two, Two know Three but Three not know One. That's neither all knowing each other nor them not meeting.
- enkid 6y agoWhat he's saying is that there is at least one set where they all know each other or they all don't know each other, not that any set of three will be that way.
- strgcmc 6y agoMaybe you're not dense, maybe you're just such a genius that pigeonhole principle proofs seem naturally obvious and tautologically true to you? :-) I found this enlightening (particularly "Sketch of a Proof"), though I also admit that it seemed fairly straightforward, with elegance borne of simplicity rather than of brilliance or cleverness: https://en.m.wikipedia.org/wiki/Theorem_on_friends_and_strangers https://en.m.wikipedia.org/wiki/Theorem_on_friends_and_stran...
- karaterobot 6y agoI keep insisting so despite mounting evidence to the contrary! Thank you for the link, this is a very good explanation.
- karmakaze 6y agoThe 'who have never met' isn't the opposite of 'all know each other', it's no two people of these three know each other. The opposite would be don't all know each other. If you imagine a six vertices arranged around a point and make any number of edges connecting them to represent knows each other. For any choice of edges, you can either find 3 vertices that are fully connected or you can find three vertices that have no connections.
- BugWatch 6y agoAdditionally, hexagons are the bestagons.