New proof reveals that graphs with no pentagons are fundamentally different
quantamagazine.org
quantamagazine.org
If anyone likes Ramsay theory and these kind of articles, I recommend Erdős' biography "The Man Who Loved Only Numbers".
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.
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."
https://blogs.scientificamerican.com/roots-of-unity/moores-l...
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.
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.
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.
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.
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.
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"
Maybe I'm incredibly dense, but this seems tautologically true, and not worth mentioning. Could somebody kindly explain what I'm missing?
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...
Thank you for the link, this is a very good explanation.
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 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 ... ;-)
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?
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 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 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.
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.
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`.
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.
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).
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...
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.
In your example, there are three who have never met (your work friend, your hobby friend, and your wife's friend).
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.
9 of the 6 people know each other = T
22 of the 6 people don't know each other = F
T || F = T
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.
Or a group of three who have never met. In your example, B, F and D have never met.
It would be significantly harder to make a ring of six.
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 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.
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 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.
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.
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.
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.
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.
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.
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...
> 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.
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.
An odd line.
Surprising given the quality of the rest of the article.
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.