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".
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.
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.
"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."
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 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.
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"
>... 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?
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.
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 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”.
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?
> 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 ... ;-)
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.
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.
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
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.
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 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.
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.
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.
"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.
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 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.
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.
[+] [-] mFixman|4 years ago|reply
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
[+] [-] strmpnk|4 years ago|reply
[+] [-] voldacar|4 years ago|reply
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.
[+] [-] thanksforfish|4 years ago|reply
"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...
[+] [-] Cerium|4 years ago|reply
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.
[+] [-] willowfine|4 years ago|reply
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
[+] [-] barbiturique|4 years ago|reply
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"
[+] [-] karaterobot|4 years ago|reply
Maybe I'm incredibly dense, but this seems tautologically true, and not worth mentioning. Could somebody kindly explain what I'm missing?
[+] [-] karmakaze|4 years ago|reply
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.
[+] [-] strgcmc|4 years ago|reply
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...
[+] [-] Moodles|4 years ago|reply
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”.
[+] [-] hoseja|4 years ago|reply
[+] [-] dooglius|4 years ago|reply
[+] [-] alanbernstein|4 years ago|reply
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?
[+] [-] q-big|4 years ago|reply
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 ... ;-)
[+] [-] BugWatch|4 years ago|reply
[+] [-] m463|4 years ago|reply
[+] [-] luxuryballs|4 years ago|reply
[+] [-] mFixman|4 years ago|reply
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.
[+] [-] Hfjfjdjfjceijfj|4 years ago|reply
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...
[+] [-] msoad|4 years ago|reply
[+] [-] ComodoHacker|4 years ago|reply
[+] [-] visarga|4 years ago|reply
[+] [-] jefurii|4 years ago|reply
See also: https://www.newyorker.com/magazine/1992/03/02/the-mountains-...
[+] [-] bena|4 years ago|reply
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.
[+] [-] zirkonit|4 years ago|reply
Or a group of three who have never met. In your example, B, F and D have never met.
[+] [-] adrianN|4 years ago|reply
[+] [-] Rerarom|4 years ago|reply
[+] [-] ouid|4 years ago|reply
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.
[+] [-] tiagod|4 years ago|reply
In your example, there are three who have never met (your work friend, your hobby friend, and your wife's friend).
[+] [-] 6gvONxR4sf7o|4 years ago|reply
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.
[+] [-] Out_of_Characte|4 years ago|reply
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.
[+] [-] x3n0ph3n3|4 years ago|reply
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.
[+] [-] joshuamorton|4 years ago|reply
[+] [-] unknown|4 years ago|reply
[deleted]
[+] [-] unknown|4 years ago|reply
[deleted]
[+] [-] TheMagicHorsey|4 years ago|reply
[+] [-] kruuuder|4 years ago|reply
[+] [-] paulyy_y|4 years ago|reply
[+] [-] WaitWaitWha|4 years ago|reply
[+] [-] mFixman|4 years ago|reply
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.
[+] [-] GordonS|4 years ago|reply
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.
[+] [-] klyrs|4 years ago|reply
http://www.cs.umd.edu/~gasarch/BLOGPAPERS/ramseykings.pdf
[+] [-] _rpd|4 years ago|reply
https://en.wikipedia.org/wiki/Graph_theory#Applications
[+] [-] einpoklum|4 years ago|reply
[+] [-] jeffrallen|4 years ago|reply
[deleted]
[+] [-] drdeca|4 years ago|reply
An odd line.
Surprising given the quality of the rest of the article.
[+] [-] dataflow|4 years ago|reply
[+] [-] lainga|4 years ago|reply