New proof reveals that graphs with no pentagons are fundamentally different(quantamagazine.org)
quantamagazine.org
New proof reveals that graphs with no pentagons are fundamentally different
https://www.quantamagazine.org/new-proof-reveals-that-graphs-with-no-pentagons-are-fundamentally-different-20210426/
115 comments
> Among those people, there’s either a group of three who all know each other, or a group of three who have never met.
Or a group of three who have never met. In your example, B, F and D have never met.
Or a group of three who have never met. In your example, B, F and D have never met.
Ramsey's theorem is a theorem about coloring. You want to color the edges of a complete graph on n vertices with k different colors. The theorem says (among other things) that you can't color the edges of the complete graph with six vertices with just two colors without creating a monochromatic triangle.
The 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"
The 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".
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 help you.
I draw 6 non collinear points on a white board in a hexagon, and explain to the students that the goal is to place red or green lines between every pair of points in the hexagon so that no red or green triangles whose vertices are all among the 6 points are formed, (here the green lines represent the relation (have met) and the red lines are (haven't met), since we are forcing every line to be colored, this is just the pair of a graph and it's complement). Most students get the idea pretty quickly, and then even get the idea that there are certain subgraphs which make a solution impossible. For instance, if I have any quadrilateral whose edges are colored red red green green, in order, then the diagonal cannot be colored either red or green. Some bright students start to get the sense that if this were possible to do, then it is likely to be possible to do by taking a graph where the condition doesn't hold and replacing one of the legs of an offending triangle.
They start to get the sense that it can't be done, and sometimes one of the students in the class will try to figure out how many graphs they would have to look through in order to prove this by "brute force". The simplest proof is to notice that a vertex with three edges of the same color incident on it is forbidden, but also is necessarily the case for every vertex.
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 help you.
I draw 6 non collinear points on a white board in a hexagon, and explain to the students that the goal is to place red or green lines between every pair of points in the hexagon so that no red or green triangles whose vertices are all among the 6 points are formed, (here the green lines represent the relation (have met) and the red lines are (haven't met), since we are forcing every line to be colored, this is just the pair of a graph and it's complement). Most students get the idea pretty quickly, and then even get the idea that there are certain subgraphs which make a solution impossible. For instance, if I have any quadrilateral whose edges are colored red red green green, in order, then the diagonal cannot be colored either red or green. Some bright students start to get the sense that if this were possible to do, then it is likely to be possible to do by taking a graph where the condition doesn't hold and replacing one of the legs of an offending triangle.
They start to get the sense that it can't be done, and sometimes one of the students in the class will try to figure out how many graphs they would have to look through in order to prove this by "brute force". The simplest proof is to notice that a vertex with three edges of the same color incident on it is forbidden, but also is necessarily the case for every vertex.
Somehow, the red/green edge example makes it easier for me to realize and not drop one of the cases.
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.
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.
> 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).
In your example, there are three who have never met (your work friend, your hobby friend, and your wife's friend).
> That in a group of at least six people, there are three people who all know each other.
If that's all it was, you could just construct a group of complete strangers as a counterexample. But as others mentioned, you left out the OR part.
If that's all it was, you could just construct a group of complete strangers as a counterexample. But as others mentioned, you left out the OR part.
"Among those people, there’s either a group of three who all know each other, or a group of three who have never met."
If your wife's friend knows no one, then you can make a group of three in which no one knows each other.
Just pick yourself, and not the person you know from from work or your hobbies. or pick the person from work and not their +1 or yourself. In this manner, in a group of 6. You inescapably have one or the other.
If your wife's friend knows no one, then you can make a group of three in which no one knows each other.
Just pick yourself, and not the person you know from from work or your hobbies. or pick the person from work and not their +1 or yourself. In this manner, in a group of 6. You inescapably have one or the other.
> That in a group of at least six people, there are three people who all know each other.
You left out the "or there are three people who have never met." In your example, C, E, and D have never met each other.
You left out the "or there are three people who have never met." In your example, C, E, and D have never met each other.
You misread. It's either 3 people who know each other or 3 who have never met. Otherwise it's trivial with a 6-cycle.
Why even bother adding an edge?
Honest answer: because I could think of the term for cycle more quickly than path.
I meant, why bother adding any edge? Just use the empty graph with 6 vertices.
Right, even trivial with a 6 vertex path. Or a 6 single vertex forest
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.
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.
Let me restate.
9 of the 6 people know each other = T
22 of the 6 people don't know each other = F
T || F = T
9 of the 6 people know each other = T
22 of the 6 people don't know each other = F
T || F = T
[deleted]
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 has been found for the general conjecture, but there has been some progress for some `H`.
The latest paper proves that the conjecture is true if `H` is a cycle of 5 graphs. Since proving this was so hard and provided so much insight, there's hope that the general conjecture can be proved without a lot more work.
⠀
Here's an actual ELI5:
There's a party where some pairs of guests know each other and some don't. A genie told you that there isn't any group of 5 people that only know two people from that group in a way that those relationships form a loop (1 — 2 — 3 — 4 — 5 — 1).
Knowing that, you reason that this cannot be a regular party. Instead, it has to be one of these two:
⒈ A class reunion, where there's a large group of people that all know each other.
⒉ A group blind date, where there's a large group of people where nobody knows anyone.
Being a smart 5-year-old the genie pushes you to publish a 19-page paper proving this, but you find out in Hacker News that some academics beat you and published it this February.
Like with most simple questions in Ramsay theory no proof or contradiction has been found for the general conjecture, but there has been some progress for some `H`.
The latest paper proves that the conjecture is true if `H` is a cycle of 5 graphs. Since proving this was so hard and provided so much insight, there's hope that the general conjecture can be proved without a lot more work.
⠀
Here's an actual ELI5:
There's a party where some pairs of guests know each other and some don't. A genie told you that there isn't any group of 5 people that only know two people from that group in a way that those relationships form a loop (1 — 2 — 3 — 4 — 5 — 1).
Knowing that, you reason that this cannot be a regular party. Instead, it has to be one of these two:
⒈ A class reunion, where there's a large group of people that all know each other.
⒉ A group blind date, where there's a large group of people where nobody knows anyone.
Being a smart 5-year-old the genie pushes you to publish a 19-page paper proving this, but you find out in Hacker News that some academics beat you and published it this February.
aaand I just realized I’m only 3
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.
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).
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).
exponential -> polynomial
Thanks, edited.
I first understood the conjecture as bounding the exponential function on the size of the graph of an element of `F_H`, but apparently the odd thing is the exponent depends solely on `H`.
I first understood the conjecture as bounding the exponential function on the size of the graph of an element of `F_H`, but apparently the odd thing is the exponent depends solely on `H`.
There's a conjecture about graphs, and the conjecture was proven true for a new specific case. So we still don't know whether the conjecture is true in general.
For understanding the conjecture itself, I think the mathematical description is the easier to comprehend than any analogy. See the intro of the Erdős–Hajnal conjecture Wikipedia article[1]. Graphs are pretty intuitive mathematical structures and the description of the conjecture only uses basic graph structures. Although maybe I'm just not clever enough to come up with a suitable analogy.
[1]: https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Hajnal_conj...
For understanding the conjecture itself, I think the mathematical description is the easier to comprehend than any analogy. See the intro of the Erdős–Hajnal conjecture Wikipedia article[1]. Graphs are pretty intuitive mathematical structures and the description of the conjecture only uses basic graph structures. Although maybe I'm just not clever enough to come up with a suitable analogy.
[1]: https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Hajnal_conj...
The article is very approachable actually. Don't be intimidated by the title. They explain this very nicely. You don't even have to know what a graph is
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 computer science, but it's a pretty close analogy. Complexity theory doesn't necessarily have a lot of direct use, but it's certainly indirectly useful to engineering, and a very useful tool for an engineer to have in their toolbelt for measuring and talking about things that are otherwise too abstract to measure. Even if you aren't inclined to study it directly yourself, don't slag on it, because you benefit from the people who do.
It's not quite the same as complexity theory in computer science, but it's a pretty close analogy. Complexity theory doesn't necessarily have a lot of direct use, but it's certainly indirectly useful to engineering, and a very useful tool for an engineer to have in their toolbelt for measuring and talking about things that are otherwise too abstract to measure. Even if you aren't inclined to study it directly yourself, don't slag on it, because you benefit from the people who do.
Thanks, great answer
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.
Because most people here are engineers, not mathematicians. The newness of mathematics has little to do with its utility, so it is reasonable to ask if there are any relevant applications.
I'm doubt there's an immediate application for this result but have there been any similar proofs in the past and what have those been applied to?
I assumed an implied AI application on graphs.
First paragraph of the article says something interesting that can be useful at parties :)
Perhaps 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.
cryptocurrency
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.
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.
Even 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.
A real world application is getting someone to respond with a real world application that would help you make money.
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. 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.
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.
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.
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.
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 walking bassline is a whole lot more similar to scales than it is anything else, and one of the most fun things to do with an instrument is to jam with other people using the fundamentals you all share.
I never felt the same way with math, because I never felt like math allowed me to put anything unique and of my own into the mix. Learning the same proof from a book that a million other kids taking geometry learned was much less interesting to me than transcribing a solo some musician played so that I could try to riff on the style they put into the world.
Sure, yeah, there's rules in music theory too. You're expected to learn them, and get graded on them in tests if you study music academically. But I don't know of any famous mathematician who ever said something like the various Duke Ellington quotes around "if it sounds good, it IS good". In the art world, similar riffs on an existing idea are everything. In math, they're just... wrong. Or at least thats the understanding I had as a student which led me to only care about the parts of math that seemed to be directly applicable to me, or really intuitive.
To phrase it another way: practicing scales can be boring. But playing a walking bassline is a whole lot more similar to scales than it is anything else, and one of the most fun things to do with an instrument is to jam with other people using the fundamentals you all share.
I never felt the same way with math, because I never felt like math allowed me to put anything unique and of my own into the mix. Learning the same proof from a book that a million other kids taking geometry learned was much less interesting to me than transcribing a solo some musician played so that I could try to riff on the style they put into the world.
Sure, yeah, there's rules in music theory too. You're expected to learn them, and get graded on them in tests if you study music academically. But I don't know of any famous mathematician who ever said something like the various Duke Ellington quotes around "if it sounds good, it IS good". In the art world, similar riffs on an existing idea are everything. In math, they're just... wrong. Or at least thats the understanding I had as a student which led me to only care about the parts of math that seemed to be directly applicable to me, or really intuitive.
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...
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...
Mathematics is indeed not taught in a proof-based manner, but I would also argue that it takes a lot of training to teach proof-based maths to primary grade students. It is far harder than teaching maths to undergrads or high schoolers. Which is the real reason it doesn't happen in schools.
> I didn't enjoy the endless calculations of long division in grade school...
Sure, everyone has their own cup of coffee. But drummers, for instance, practice the same beats over and over again for dozens of hours to perfect them. Not very different from doing long division over and over again.
> I didn't enjoy the endless calculations of long division in grade school...
Sure, everyone has their own cup of coffee. But drummers, for instance, practice the same beats over and over again for dozens of hours to perfect them. Not very different from doing long division over and over again.
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.
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.
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).
The 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.
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.
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.
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.
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!
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
http://www.cs.umd.edu/~gasarch/BLOGPAPERS/ramseykings.pdf
This 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
A research grant application maybe? :-P
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
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.
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.
I 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.
Their audience is me, a curious not-very-technical layman who is interested in the concepts but bored by the details!
Granted, I'm not sure how common this is.
I do worry about Gell-Mann amnesia with Quanta, but I comfort myself that usually nobody has a stake in distorting this or that number theory thingamajig or physics quandary. However... I'm sure there are academic infights and research tug-of-war to which I'm blissfully blind.
Granted, I'm not sure how common this is.
I do worry about Gell-Mann amnesia with Quanta, but I comfort myself that usually nobody has a stake in distorting this or that number theory thingamajig or physics quandary. However... I'm sure there are academic infights and research tug-of-war to which I'm blissfully blind.
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.
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.
That 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-l...
"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-l...
That comment just wants me to fight aliens. What's wrong with me?
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 something like 10^200 graphs.
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 something like 10^200 graphs.
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). (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.
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.
I was talking about graphs up to their representation. You are talking about graphs up to isomorphism. Recognizing that two graphs are isomorphic is a potentially tricky problem. Generating them by isomorphism class is certainly not going to be the naive approach.
But suppose that we are able to do so. How much does this do for us? Well, it can help us by a factor of at most n!, because you generate isomorphic graphs by permuting the vertices. Which for 43 is around 6.04152630633738e+52. For 48 is around 1.24139155925361e+61. Those are big savings to be sure, but are still dwarfed by the size of the search space.
So the next thing to do is to not only try to look at each graph up to isomorphism once, but to somehow generate them in an order that makes it likely that you find cliques or independent sets early. Thereby letting you prune out big chunks of the search space. With the ability to start different computers out in different ranges so we can parallelize the search. But by now we're well down on the path to something that is very much not a naive search.
But suppose that we are able to do so. How much does this do for us? Well, it can help us by a factor of at most n!, because you generate isomorphic graphs by permuting the vertices. Which for 43 is around 6.04152630633738e+52. For 48 is around 1.24139155925361e+61. Those are big savings to be sure, but are still dwarfed by the size of the search space.
So the next thing to do is to not only try to look at each graph up to isomorphism once, but to somehow generate them in an order that makes it likely that you find cliques or independent sets early. Thereby letting you prune out big chunks of the search space. With the ability to start different computers out in different ranges so we can parallelize the search. But by now we're well down on the path to something that is very much not a naive search.
I 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
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
Does 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"
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]
What is a good book to read to learn about graph theory?
If 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.
Arachnophobes beware
> the pentagon (or really any five-sided polygon)
An odd line.
Surprising given the quality of the rest of the article.
An odd line.
Surprising given the quality of the rest of the article.
I don't really tend to think of non-convex five-sided polygons as pentagons (even if they technically are), and I'm guessing they wanted to emphasis those are included too.
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.
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.
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.
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.
The pointlessness in the distinction is that we're talking about graphs defined by their vertices and edges, not how they're drawn. (Planar graphs about how they 'could' be drawn not withstanding.)
No, it isn't; a regular pentagon has all equal side lengths (as described) and all equal interior angles (not as described).
>... 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?
Maybe I'm incredibly dense, but this seems tautologically true, and not worth mentioning. Could somebody kindly explain what I'm missing?
The '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.
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.
I would describe it as follows, maybe a little easier to visualize. Draw six dots, draw either a red or a blue line from every dot to every other dot. You must draw either a completely red triangle or a completely blue triangle. Personally I don't think it sounds intuitive when stated like that!
Thanks, personally I found this the easiest way to think about it!
Thanks, that clarifies it!
Maybe 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_stran...
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_stran...
I keep insisting so despite mounting evidence to the contrary!
Thank you for the link, this is a very good explanation.
Thank you for the link, this is a very good explanation.
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”.
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
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
It's not true for 5 people if the "has met" graph is a pentagon, does your intuition here still work?
To a robot, all mathematical truths are tautologies, right?
Perhaps you could imagine reading that statement with both occurrences of "three" replaced with blanks. Do you think you could confidently fill them in without more than a moment's thought?
Perhaps you could imagine reading that statement with both occurrences of "three" replaced with blanks. Do you think you could confidently fill them in without more than a moment's thought?
> Maybe I'm incredibly dense, but this seems tautologically true, and not worth mentioning. Could somebody kindly explain what I'm missing?
If this seems so trivial to you, simply write down the proof. If you are not really mathematically gifted, you will soon see where the problem is ... ;-)
If this seems so trivial to you, simply write down the proof. If you are not really mathematically gifted, you will soon see where the problem is ... ;-)
I 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-...
See also: https://www.newyorker.com/magazine/1992/03/02/the-mountains-...
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.