To learn more, read the article on the Quanta Magazine website www.quantamagazine.org/only-computers-can-solve-this-map-coloring-problem-from-the-1800s-20230329/
I once attended a talk on the four colour theorem. The professor explained the history of the problem and gave the proof of the five colour theorem. He then told us that if we now tried to prove the four colour theorem at home, we would find a proof and it would be wrong. Sure enough, when I tried to adapt the proof of the five colour theorem to prove the four colour theorem I succeeded quite quickly, and it took me considerably longer to realise where the subtle mistake was. (And I only found the mistake because I KNEW that there was one.)
Yess this gives me same sensation as the konigsberg bridge problem, aways having the feeling that you can do it! but you also know that is impossible XD
With my rough back of the napkin math, 1000 hours of 1970s computer time , on a modern smartphone would take appropriate 2 hours, even with poor algorithm search. If an exhaustive search was done then, why would it be invalid now?
@@_FFFFFF_ the 1970 computer-assisted proof is valid, the method that was used in the 1800s to "prove" the 4-colour theorem can be used to prove that 5 colours suffice, but it very subtly goes wrong for 4 colours. I think the method works by assuming N colours are not enough, taking a minimal map that needs N+1 colours, then finding chains of countries in alternating colours and showing that you can flip them in such a way that you free up a colour for the country that needed the N+1-th colour. So contradiction, which means you have shown that N are enough. So with N=5 you can make this work (and you can explain it to a high school student), and with N=4 it almost works but not quite.
As a mapmaker, I never expected this to be an actual discussion in math! I’ve had to deal with the 4/5 color theories before when making state maps or county maps. but I never considered the math behind it!
@@spltorky colors can repeat. You can even have ten countries touching one country (call it X), you just reuse three colors so that no color touches another color, and then you can have the fourth color for X
Such a bizarre problem. Normally topological problems like these wind up having a basic explanation when you peel it back; this one has a proof so long we can't read it end to end! Very cool.
The proof of the four colour theorem may be extremely long, but if memory serves, it was still verified (by a team) after the computer produced it. It has also been verified by computers, which is ironically often seen as more rigorous than human verification, since it has to be written in pure logic, making misleading steps impossible.
Indeed, the whole proof has now been converted into a form that can be checked by a proof checker. The proof checker program is simple enough that its correctness can be verified by a human. Converting a proof into a form that a computer can check is a huge amount of work, but I suppose AI wil lbe able to help us with that in the near future.
Is there a correlation between the length of a mathematical statement, problem or question, and the length of corresponding proofs? What kinds of proofs can be shown to be incompressible? When taking statements and corresponding proofs, then applying a set of diverse 'hash functions' on them - will interesting relations between the three leave traces, be preserved or even appear in a different structure?
@@DarkSkay When looking at the proof of a specific theorem, you generally want to slightly weaken some axioms, and determine whether the theorem still holds. A slightly weaker version of geometry doesn't allow for similar triangles per reflection, and also doesn't have area. Here, the Pythagorean theorem does not necessarily hold. To proof the Pythagorean theorem, you would have to use the similarity of two triangles that are mirrored images of each other, or use area. This only works on relatively simple proofs though. The proof of the four colour theorem is so immensly long that this approach is unrealistic here.
@@caspermadlener4191 Thank you! Sometimes, the more I think about what's happening, 'self-constructing', almost organically growing, emerging in maths, the more philosophically mysterious it appears to me. Not only is the number of questions infinite, intuitively the uncountable oceans of 'interesting' ones seem as well - like a natural affinity or family ties between abstract logic structures and the mind. Curiosity never running out of projections and destinations.
The four colors only hold true for maps without exclaves/enclaves. If you want to color exclaves/enclaves in the same color as the country they belong to then in some cases you might need additional colors.
Try it yourself and you soon figure it out. You could theoretically place hundreds of small enclaves within a country. And if you do that for every country than every country theoretically borders hundreds of countries at the same time and you need hundreds of colors. Of course, this is extreme and doesn’t happen in real life. A real life example. If you would include bodies of water the are territorial and color them as if their land, The Netherlands, Belgium, Germany all border each other and the UK. So, all four need their own colors. Now Belgium, Germany and the UK all border France, (UK borders France across the channel and part Atlantic Ocean) so France would need the same color as The Netherlands. But now, in the Caribbean France borders The Netherlands. So, a fifth color is needed.
I'm guessing here but I would think including enclaves and exclaves in the map results in non-planar graphs, so the initial assumptions on the question have changed, from a purely 'mathematical' point of view
@@ilfedarkfairyIt makes the maths really easy, because there is a simple way to construct a map with enclaves that can't be colored with n colors or fewer (for any given n). Just take n+1 countries, make them each have an enclave of every other country and boom, you need n+1 colors
What about enclaves and exclaves? For example, consider a map with 5 countries, where one of the countries has a small territory inside every other country.
from my understanding, with enclaves and exclaves there is no maximum amount of colors. no matter how many colors you allow, you can always construct a map that needs more than that. for the same reason, countries that only share a corner do not count as adjacent.
yeah exactly ignoring mathematics it is extremely simple to disprove this theory by looking at actual maps. Hell even in the 1800s this was obvious, exclaves were far more common and far more cursed than today, they just needed to think about the german confederation or later the internal borders of the german empire
easy, let's say you have south africa and lesotho. if south africa is colored red, you can color lesotho any of the other 3 colors, because it only borders one country.
Fascinating story! While I've never had any formal education in graph theory, and unfortunately probably never will, it does appear to be a very approachable and rich subject, ripe for plenty more engaging content such as this video. Might have to pick up a textbook on the subject sometime!
I guarantee you do not talk like that in real life. Absolutely no chance. Sound like Jordan Peterson, when he babbles on and forgets what he started talking about in the first place. Catch my drift?
Assuming that the unavoidable set of 1,936 configurations was rigourously proved, what the computer did was not find any counterexamples to the four-color requirement. It's like disproving Riemann or Fermat by finding one counterexample. The search space is finite, every combination was checked, no counterexamples were found, QED.
This is genuinely interesting. I remember reading about the four color theorem in my mathematical logic class and trying to apply Kőnig's lemma to it (with no success).
6:15 Altgeld Hall at UIUC! I'm doing my math undergrad there. What a beautiful winter picture of the math department building. They're doing renovations right now! :)
Of course the ironic thing is that the *original* theorem is actually a five-colour theorem- because there is always an implicit decision to ignore the *oceans* that surround the area talking about- which on a map will either be blue or white but cannot be considered 'blanks' or 'non-existent' because they're a defined boundary in and of themselves that connects to every point on the outer edge of the graph/map. And if your area has defined oceanic *and* land borders external to the area being coloured that's 6 colours for the final work regardless. And of course Mt. Etna is actually home to a point where 11 municipalities meet (one in fact being enclosed by two arms of another) meaning you just have to shrug and decide that vertices don't count as boundaries. And the whole system just ignores that actual geographical areas might not be contiguous which means that an entity can very easily have borders with *more* 'points' than the graph theoretically suggests. Which is probably why cartographers have never particularly cared about this.
Well, you can assign one of those four colours to the oceans, but lakes will probably not work well. And yes, point borders and exclaves mess the system up, but originally even proving the (now trivial) six colour theorem was a success. Asking if six is the best possible result is only natural.
The skepticism surrounding proofs generated by early computing has a lot of parallels to the current unease surrounding AI generated content today. Doctors and lawyers in particular are having their paradigms shifted by neural networks trained to solve problems that were considered very tough problems only a few short years ago. Just goes to show that the perceptions of the problems we face are constantly shifting!
Fascinating and consequential story. Just one point, in "The Mathematical Tourist", Ivars Peterson (1988) and widely cited in other literature, it is stated that the problem was first proposed in a letter in 1852 written by British graduate student Francis Guthrie to his younger brother, and not from Augustus de Morgan to William Hamilton. Just a point of interest and many thanks - Dave
Where did the unavoidable set came from? Certainly you could draw much more edges from a point than 5? Or did they actually look at maps and couldn't find countries that have more than 5 connections?
It is a nice video. But it is a mistake at 6:45 to say that every map that contains one of the unavoidable configurations is proven 4-colorable. The actual point is that if a map contains one of the configurations, then it provably is not a minimal counterexample.
I'm really confused on the minimal counterexample argument, because I get it in theory, but here he seemed to take some random variation, show you can do it with 4 colours, and say that proves you can with any map, can someone please explain
The image is not the minimal counterexample. The idea is that IF a minimal counterexample existed, THEN we show that it is not a minimal counterexample (either by solving it or making it smaller) and THEREFORE no minimal counterexample exists. These proofs by contradiction are a bit tricky and really hard to illustrate, since the object you are talking about does not actually exist.
If you represent the areas of any map with 4 or more areas with a vertices and draw a line between each bordering vertices, (as mentioned in the video), but then translate the vertices into 4 vertices in three dimensions, you will get a three sided pyramid with each vertices being a point and each line connecting a bordering area being an edge for any possible arrangement of four areas. And then if you project this pyramid back onto two dimensions with a light, then one of the connecting lines between the vertices must cross another line, therefore those two vertices (areas) cannot be bordering each other and can be colored using the same color. I am not a mathematician, but is this not a proof?
A three-sided pyramid, aka a tetrahedron, can be flattened without the edges crossing by depicting it as a triangle (the base of the pyramid) with a vertex (the peak) in the center.
Only issue I have about this theorem is: what if 5 countries touch each other in the same point, like a 5-way star? Or doesn't that single point count as 'bordering'?
Maps tend to be 2D. You don't find a map with an upstairs... or do you? House plans might have any number of "staircases" to the next floor, that has rooms with different coloured carpets. How many different colours of carpet are needed to ensure that the adjacent room doesn't have the same colour? Have I accidentally set another level of challenge?
No, because it can be easily proven that there is no answer (the answer is infinity) [======================== [=^=][=^=][=^=][=^=][=^=][=^=][= There can be one large room upstairs that can be connected to all the rooms downstairs
Really well made again. I also like Kempe's (fake) proof, I even once released an April fool's day video proving the four color theorem with it. Despite this, I didn't really understand the idea behind the valid computer-generated proof, and this video just explained it so clearly. Similarly as with Langlads program, it is impressive how you can go deeper than ordinary math youtubers in such a short time and remain easily understandable. By the way coincidentally, I am now working on computer / formal mathematics -- I would like computers to be able to one day solve IMO problems but there is still a long way to go.
Basically they constructed an unavoidable set of configurations, that is to say, every planar graph provably contains at least one of these. Also the configurations are chosen so that they all are "likely to be" reducible, in the same sense as in Kempe's failed proof. Finally a computer program is used to verify that each configuration is indeed reducible. When they hit on a set of configurations that works, they were done.
You can prove this theorem yourself by opening up MSPaint (or any other drawing program) and trying to make 5 different shapes all touch one another. It's trivial to get all three to touch each other, and you can easily make all four shapes touch one another. But when you try to add a 5th, they start blocking each other and getting in the way. Make room for one shape/color to touch another, but then you've cut off another shape/color. This happens no matter what you try to do. I'd say this is also a property of geometry and the limits of 2d space.
But how do you prove that its impossible to have 5 vertices that connect completely with each other? We can see so its intuitive but maybe we are missing something beyond our intuition and visualization?
@@arpitkumar4525 I guess I don't get what you're asking. If we demonstrate by example that the task is impossible, and exhaust all possibilities, then is that not already proof?
All natural numbers are interesting. If this were false, there would be a smallest non-interesting natural number, and that number would be very interesting. QED
I understood nothing from this video. On one hand, it makes me kinda mad and a bit sad, but also happy that we have so many people understanding it. Please, never support the de-education of peoples.
The idea is that if there were maps that could not be coloured with four colours, we look at a minimal one. Then we delete some countries. As the new map is smaller than the minimal one that requires more than five colours, it can be coloured with four colours. No we add the countries back and prove that the map can still be coloured with four colours. The complicated part is proving that there is a set of subgraphs so that each graph without crossing lines contains at least one of them. If that is proven, you need to find recolouring algorithms for every one of those subgraphs that work with four colours or less.
👍 for admitting that you don't understand this stuff. If everybody were as honest as you there would be no Covidiots, conspiracy theories, Antivaxxers, .... I guess. Only yesterday I told my daughter that it is not necessarily useless to learn things in school which one will never need again in life - it at least makes one realize that there are things one does not understand but that there ore others who do; so if there is a problem ( like climate change, Covid, ... ), just shut up and let them do their work ( and listen to them ).
No, you need to consider that there's more countries than just the ones bordering the one that you're colouring right now, some other neighbours of the neighbouring countries might have made that colouring invalid already
@@arpitkumar4525 Get out a piece of paper, or open some other drawing app. First you put one dot anywhere near the middle. Then you draw another dot nearby and connect with a line. The goal here is to add dots, or vertices, which connect to *all other* dots, but their lines *do not* intersect. These first two steps are trivial, and the only "intersection" you could possibly have is if you put the two dots right on top of each other. Your next task is a third dot, which is also trivially easy. Place the dot anywhere else on the paper that isn't on the line you just drew. Connect all the vertices and now you have a triangle. When you add the fourth dot, this is your first meaningful decision. You only have two options: you can put the dot inside the triangle, or outside it. These are literally your only options, unless you want to put your dot on one of the other lines or dots you drew, which is automatic failure. If you put your dot inside the triangle you had, you can easily connect it to all the other dots and still satisfy the requirements. If you put your dot on the outside, it's possible that you can't. You would have to position the dot so that it is essentially extending from a point on the triangle in order for your new dot to connect to the back two vertices. If you do not position this dot correctly, it can't reach the vertex in the back without crossing an existing line. If you think about what we've done, it is logically impossible to have arrived at any other outcomes. And if you think about it more, both examples we end up with are pretty much the same configuration, but perhaps stretched in certain ways. The last thing to do is try to add a 5th dot which connects to all the vertices, but does not cross any lines. And here is where we run into a problem. Place the dot anywhere inside the bigger triangle, and it is boxed in and can only reach 3 of the 4 previous vertices. Place the dot outside the large triangle, and although you can reach all the outer vertices, you can never reach the inner vertex without crossing a line. This truth is absolutely undeniable, and therefore it is a form of proof. If you are looking for something purely mathematical, I don't think anyone in the comments section has any time to entertain you.
This would make a great project for math students at any age. Ask them, color in this map, so that no neighbors are the same color, and try and use the least amount of colors possible. See who wins.
You raise a good point: While the theorem proves that you can colour any map in four colours, it does not tell you HOW. For a very complicated map you will run into issues, if you you try it by hand. Then you may need some of those complex recolouring algorithms.
With enclaves and exclaves the number is not limited, as each country could have an exclave in each other country. Then each country would need a different colour.
What would a human understandable proof be worth, as in how could the prover's efforts be rewarded? And I don't mean BS such as the accomplishment being reward in itself. I mean financial or livelihood gain.
That's not necessary, the proof uses the fact that each map has *at least one* such country, it focuses on that country to reduce the map, proving the counterexample false
1:07 Evidence might be that color was expensive to produce at the time. So, it could be a valid reason, and cartographers are more mathematical than the average joe.
The Four Color Theorem, which states that any map can be colored with only four colors without any two adjacent regions sharing the same color, was a longstanding problem in mathematics that was finally solved in 1976 with the use of computers. The problem was initially posed by Francis Guthrie, who wondered if the four-color rule applied to all maps. Mathematicians attempted to solve the problem for decades but couldn't find a proof that satisfied everyone. It wasn't until Kenneth Appel and Wolfgang Haken developed a proof that relied heavily on computers that the problem was finally solved. This sparked a debate about the role of computers in mathematics and what it means to be a mathematician. The proof has wide-ranging applications, from planning wedding seating arrangements to assigning frequencies to radio stations. The problem was originally thought to have come from cartographers, but it was actually posed by mathematicians. The problem can be simplified by converting maps to planar graphs, which are easier to analyze. Mathematicians use graph theory to study relationships between objects, and this helps them analyze the Four Color Theorem. Although the proof is not without controversy, it stands as a testament to the power of computers in mathematics and the innovative thinking of mathematicians.
on second thoughts. some more stuff. Haken died in October last year. his family are also a bunch of geniuses. armin proved some stuff which Pudlak mentions in "proofs as games". the idea of "gameifying" proofs to use human "game play" intuition is interesting. but the actual fact that it works as a strategy is fun. even when it doesnt, which harks back to this problem as a game (see "the map-coloring game" by Bartnicki, Grytczuk, Kierstead and Zhu. as expected, popularised by Gardner) it reveals some great facts about strategy, like Daltonism (colorblindness) might force a player who suggests the game to another to change the game to something similar and yet they can still get a winning stategy that can be back-ported to the original game!!
take lesotho and separate it in four quarters, all of them will touch each other and will be four colors, now add south africa back and BAM the four color theorem is wrong unless you dont count corners which is fair
The theorem doesn't count corners If corners are counted, any amount of colours may be necessary because any amount of countries can touch in one point
Sorry to sound crude and dumb but why does colouring of a map matter?? Can't you just colour it whatever you want? Again sorry to sound dumb, i am not really a mathematician.
That is the part I don't understand. Why wouldn't 1 rectangle touch 20 others?@@0106johnny Therefore, requiring you to have 20 colors so no two colors touched...
My proof (if you can call it that) is simpler: the main stress is on the borders. Every country on a map has either an odd or an even number of bordering countries. An even number only requires 2 extra colours to contrast with the home country, while an odd number requires three extra: so no configuration of a country and its neighbours needs more than 4 total colours to distinguish them from one another. This is true of every such instance in 2-D. Each neighbouring country has exactly the same scenario. Exclaves won’t always work though because of an unviable rigidity in such an extension of the system. So it’s a problem of numbers after all. A neat little piece of history with the computer proof being finally clearly a proof after all, which I had previously doubted.
That only proves it for one country and all its neighbours. Both those countries have neighbours themselves. Every graph with no crossing lines can represent a map. So their are endless possibilities.
and each such country is subject to exactly same constraints and opportunities. I'm not yet convinced I'm wrong, but if you could explain it in simple terms . . .?@@skyscraperfan
@@skyscraperfanso iin that case, you can have canada swallow usa to create The Great Canadian Empire, with X+Y states....whiiiich still follow the topological rule that that other person mentioned. The 4CT is pro-imperialist, and thus, I reject it, just fyi.
The simplest shape is a triangle which has three neighbors plus itself = four colors needed = more complex shapes may need less but couid never need more.
When I was a kid I just assumed it was for the same reason that you cannot have more than four shapes each touch each other simultaneously on a 2D plane. Not sure why that would require a complex proof lol.
This proves that you can colour a country and its neighbouring countries in just 4 colours, but when you go to the neighbours of the neighbours you might run into a conflict with the colours you've already used, and it's not as simple to prove there's no such conflict
To learn more, read the article on the Quanta Magazine website www.quantamagazine.org/only-computers-can-solve-this-map-coloring-problem-from-the-1800s-20230329/
I once attended a talk on the four colour theorem. The professor explained the history of the problem and gave the proof of the five colour theorem. He then told us that if we now tried to prove the four colour theorem at home, we would find a proof and it would be wrong. Sure enough, when I tried to adapt the proof of the five colour theorem to prove the four colour theorem I succeeded quite quickly, and it took me considerably longer to realise where the subtle mistake was. (And I only found the mistake because I KNEW that there was one.)
Yess this gives me same sensation as the konigsberg bridge problem, aways having the feeling that you can do it! but you also know that is impossible XD
With my rough back of the napkin math, 1000 hours of 1970s computer time , on a modern smartphone would take appropriate 2 hours, even with poor algorithm search. If an exhaustive search was done then, why would it be invalid now?
@@_FFFFFF_ the 1970 computer-assisted proof is valid, the method that was used in the 1800s to "prove" the 4-colour theorem can be used to prove that 5 colours suffice, but it very subtly goes wrong for 4 colours.
I think the method works by assuming N colours are not enough, taking a minimal map that needs N+1 colours, then finding chains of countries in alternating colours and showing that you can flip them in such a way that you free up a colour for the country that needed the N+1-th colour. So contradiction, which means you have shown that N are enough. So with N=5 you can make this work (and you can explain it to a high school student), and with N=4 it almost works but not quite.
How do you deal with multiple enclaves?
@@tasty_fish The four/five colour theorem ignores them.
0:43 Holding down a map with solids of constant width - I like this guy already.
😂
I'm always impressed by the quality of these videos. Your cameramen, editors and VFX people must be very talented :)
The VFX is absolutely high-tier!
Music and audio too!
As a mapmaker, I never expected this to be an actual discussion in math! I’ve had to deal with the 4/5 color theories before when making state maps or county maps. but I never considered the math behind it!
Samee
@@spltorky colors can repeat. You can even have ten countries touching one country (call it X), you just reuse three colors so that no color touches another color, and then you can have the fourth color for X
How old are you?
Such a bizarre problem. Normally topological problems like these wind up having a basic explanation when you peel it back; this one has a proof so long we can't read it end to end! Very cool.
The proof of the four colour theorem may be extremely long, but if memory serves, it was still verified (by a team) after the computer produced it.
It has also been verified by computers, which is ironically often seen as more rigorous than human verification, since it has to be written in pure logic, making misleading steps impossible.
Indeed, the whole proof has now been converted into a form that can be checked by a proof checker. The proof checker program is simple enough that its correctness can be verified by a human.
Converting a proof into a form that a computer can check is a huge amount of work, but I suppose AI wil lbe able to help us with that in the near future.
Is there a correlation between the length of a mathematical statement, problem or question, and the length of corresponding proofs? What kinds of proofs can be shown to be incompressible? When taking statements and corresponding proofs, then applying a set of diverse 'hash functions' on them - will interesting relations between the three leave traces, be preserved or even appear in a different structure?
@@DarkSkay When looking at the proof of a specific theorem, you generally want to slightly weaken some axioms, and determine whether the theorem still holds.
A slightly weaker version of geometry doesn't allow for similar triangles per reflection, and also doesn't have area. Here, the Pythagorean theorem does not necessarily hold.
To proof the Pythagorean theorem, you would have to use the similarity of two triangles that are mirrored images of each other, or use area.
This only works on relatively simple proofs though. The proof of the four colour theorem is so immensly long that this approach is unrealistic here.
Yeah, if _one_ value is wrong, the computer won't get it
@@caspermadlener4191 Thank you! Sometimes, the more I think about what's happening, 'self-constructing', almost organically growing, emerging in maths, the more philosophically mysterious it appears to me. Not only is the number of questions infinite, intuitively the uncountable oceans of 'interesting' ones seem as well - like a natural affinity or family ties between abstract logic structures and the mind. Curiosity never running out of projections and destinations.
Writing this computer proof in IBM 370 assembly language seems like a herculean feat of programming.
The animations at 2:13 are seamless and awesome. Great video :)
No they are not, one of the joints was wrongly drawn.
Is that true?
Give the editor a raise! Good job!
The four colors only hold true for maps without exclaves/enclaves. If you want to color exclaves/enclaves in the same color as the country they belong to then in some cases you might need additional colors.
Is that right?
Try it yourself and you soon figure it out. You could theoretically place hundreds of small enclaves within a country. And if you do that for every country than every country theoretically borders hundreds of countries at the same time and you need hundreds of colors. Of course, this is extreme and doesn’t happen in real life.
A real life example. If you would include bodies of water the are territorial and color them as if their land, The Netherlands, Belgium, Germany all border each other and the UK. So, all four need their own colors. Now Belgium, Germany and the UK all border France, (UK borders France across the channel and part Atlantic Ocean) so France would need the same color as The Netherlands. But now, in the Caribbean France borders The Netherlands. So, a fifth color is needed.
I'm guessing here but I would think including enclaves and exclaves in the map results in non-planar graphs, so the initial assumptions on the question have changed, from a purely 'mathematical' point of view
Yeah, I'm kinda suprised that this was not mentioned. This completly changes the maths behind the problem, adding extra dimensions.
@@ilfedarkfairyIt makes the maths really easy, because there is a simple way to construct a map with enclaves that can't be colored with n colors or fewer (for any given n). Just take n+1 countries, make them each have an enclave of every other country and boom, you need n+1 colors
How can this video have 731 views when there's only 600 people on earth?
131 from another universe 😂😂
off by one error
You can watch the video more than once. All of the views actually only come from 13 different people
😅
Im pretty sure people dont exist, its just a random bunch of numbers that increases with no reason.
What about enclaves and exclaves? For example, consider a map with 5 countries, where one of the countries has a small territory inside every other country.
The theorem only holds for contiguous regions. Once you add non-contiguous regions like enclaves and exclaves, it starts breaking down.
from my understanding, with enclaves and exclaves there is no maximum amount of colors. no matter how many colors you allow, you can always construct a map that needs more than that.
for the same reason, countries that only share a corner do not count as adjacent.
yeah exactly ignoring mathematics it is extremely simple to disprove this theory by looking at actual maps. Hell even in the 1800s this was obvious, exclaves were far more common and far more cursed than today, they just needed to think about the german confederation or later the internal borders of the german empire
easy, let's say you have south africa and lesotho. if south africa is colored red, you can color lesotho any of the other 3 colors, because it only borders one country.
Fascinating story! While I've never had any formal education in graph theory, and unfortunately probably never will, it does appear to be a very approachable and rich subject, ripe for plenty more engaging content such as this video. Might have to pick up a textbook on the subject sometime!
You definitely should! 😁👍🏼
I guarantee you do not talk like that in real life. Absolutely no chance.
Sound like Jordan Peterson, when he babbles on and forgets what he started talking about in the first place.
Catch my drift?
@@richross4781 Wut?
@@richross4781bruh nobody types how they talk irl n this person here did not lose track of their original poiny
quanta always puts out gold. you guys have amazing interesting content
❤
Assuming that the unavoidable set of 1,936 configurations was rigourously proved, what the computer did was not find any counterexamples to the four-color requirement. It's like disproving Riemann or Fermat by finding one counterexample. The search space is finite, every combination was checked, no counterexamples were found, QED.
This is genuinely interesting. I remember reading about the four color theorem in my mathematical logic class and trying to apply Kőnig's lemma to it (with no success).
6:15 Altgeld Hall at UIUC! I'm doing my math undergrad there. What a beautiful winter picture of the math department building. They're doing renovations right now! :)
great quality of content and visuals!!! love it
The quality of this video is impressive. Thank you.
Of course the ironic thing is that the *original* theorem is actually a five-colour theorem- because there is always an implicit decision to ignore the *oceans* that surround the area talking about- which on a map will either be blue or white but cannot be considered 'blanks' or 'non-existent' because they're a defined boundary in and of themselves that connects to every point on the outer edge of the graph/map. And if your area has defined oceanic *and* land borders external to the area being coloured that's 6 colours for the final work regardless.
And of course Mt. Etna is actually home to a point where 11 municipalities meet (one in fact being enclosed by two arms of another) meaning you just have to shrug and decide that vertices don't count as boundaries.
And the whole system just ignores that actual geographical areas might not be contiguous which means that an entity can very easily have borders with *more* 'points' than the graph theoretically suggests.
Which is probably why cartographers have never particularly cared about this.
Well, you can assign one of those four colours to the oceans, but lakes will probably not work well. And yes, point borders and exclaves mess the system up, but originally even proving the (now trivial) six colour theorem was a success. Asking if six is the best possible result is only natural.
The skepticism surrounding proofs generated by early computing has a lot of parallels to the current unease surrounding AI generated content today. Doctors and lawyers in particular are having their paradigms shifted by neural networks trained to solve problems that were considered very tough problems only a few short years ago. Just goes to show that the perceptions of the problems we face are constantly shifting!
Fascinating and consequential story. Just one point, in "The Mathematical Tourist", Ivars Peterson (1988) and widely cited in other literature, it is stated that the problem was first proposed in a letter in 1852 written by British graduate student Francis Guthrie to his younger brother, and not from Augustus de Morgan to William Hamilton. Just a point of interest and many thanks - Dave
Where did the unavoidable set came from? Certainly you could draw much more edges from a point than 5? Or did they actually look at maps and couldn't find countries that have more than 5 connections?
Very interesting. Thank you.
It is a nice video. But it is a mistake at 6:45 to say that every map that contains one of the unavoidable configurations is proven 4-colorable. The actual point is that if a map contains one of the configurations, then it provably is not a minimal counterexample.
Unfortunately this is only true for 2 dimensional maps, is there a known minimum for 3 dimensional maps as those become more common?
My old friend Network theory strikes again. Easily the most intriguing aspect of my mathematics degree
I'm really confused on the minimal counterexample argument, because I get it in theory, but here he seemed to take some random variation, show you can do it with 4 colours, and say that proves you can with any map, can someone please explain
The image is not the minimal counterexample. The idea is that IF a minimal counterexample existed, THEN we show that it is not a minimal counterexample (either by solving it or making it smaller) and THEREFORE no minimal counterexample exists. These proofs by contradiction are a bit tricky and really hard to illustrate, since the object you are talking about does not actually exist.
If you represent the areas of any map with 4 or more areas with a vertices and draw a line between each bordering vertices, (as mentioned in the video), but then translate the vertices into 4 vertices in three dimensions, you will get a three sided pyramid with each vertices being a point and each line connecting a bordering area being an edge for any possible arrangement of four areas. And then if you project this pyramid back onto two dimensions with a light, then one of the connecting lines between the vertices must cross another line, therefore those two vertices (areas) cannot be bordering each other and can be colored using the same color. I am not a mathematician, but is this not a proof?
A three-sided pyramid, aka a tetrahedron, can be flattened without the edges crossing by depicting it as a triangle (the base of the pyramid) with a vertex (the peak) in the center.
Does Four-Color Theorem also work for theoretical exclaves? Or does it assume all regions are contiguous?
It does not work on enclaves in some cases, because in math the term "map" does not have exclaces
Only issue I have about this theorem is: what if 5 countries touch each other in the same point, like a 5-way star? Or doesn't that single point count as 'bordering'?
It doesn't.
Really well explained and excellent animations. Love it!
Would love to collaborate with Quanta on the history of computers making mathematical conjecture
You know all that footage is from the 50’s and not the 70’s right?
Maps tend to be 2D.
You don't find a map with an upstairs... or do you?
House plans might have any number of "staircases" to the next floor, that has rooms with different coloured carpets.
How many different colours of carpet are needed to ensure that the adjacent room doesn't have the same colour?
Have I accidentally set another level of challenge?
No, because it can be easily proven that there is no answer (the answer is infinity)
[========================
[=^=][=^=][=^=][=^=][=^=][=^=][=
There can be one large room upstairs that can be connected to all the rooms downstairs
Really well made again. I also like Kempe's (fake) proof, I even once released an April fool's day video proving the four color theorem with it. Despite this, I didn't really understand the idea behind the valid computer-generated proof, and this video just explained it so clearly. Similarly as with Langlads program, it is impressive how you can go deeper than ordinary math youtubers in such a short time and remain easily understandable. By the way coincidentally, I am now working on computer / formal mathematics -- I would like computers to be able to one day solve IMO problems but there is still a long way to go.
Superb video, thanks!!!
My question is, how do they know there are a finite number of unavoidable sets? (1,936 sets)
Basically they constructed an unavoidable set of configurations, that is to say, every planar graph provably contains at least one of these. Also the configurations are chosen so that they all are "likely to be" reducible, in the same sense as in Kempe's failed proof. Finally a computer program is used to verify that each configuration is indeed reducible. When they hit on a set of configurations that works, they were done.
Omg that's Dickinson College in Denny Hall!
The explanation and animation are both top notch , Thanks you for the video 😊
Mantap!
Next is ... coloring problem in arbitrary dimension
You can prove this theorem yourself by opening up MSPaint (or any other drawing program) and trying to make 5 different shapes all touch one another. It's trivial to get all three to touch each other, and you can easily make all four shapes touch one another. But when you try to add a 5th, they start blocking each other and getting in the way. Make room for one shape/color to touch another, but then you've cut off another shape/color. This happens no matter what you try to do. I'd say this is also a property of geometry and the limits of 2d space.
But how do you prove that its impossible to have 5 vertices that connect completely with each other? We can see so its intuitive but maybe we are missing something beyond our intuition and visualization?
@@arpitkumar4525 I guess I don't get what you're asking. If we demonstrate by example that the task is impossible, and exhaust all possibilities, then is that not already proof?
@@taleladar But how do you know you exhausted all possibilities? There might be something you didn't consider?
Here way before 1m views, but soon you'll get there. Great material, *proof* that is possible to make a great and informative math video in
4:42 This is another reason why peer review is so important
why is David S. Richson’s voice SO familiar?!
So nice sir g.
"Suppose you want to color the map with four or fewer colors, if you can't there exist smallest map of such"
All natural numbers are interesting. If this were false, there would be a smallest non-interesting natural number, and that number would be very interesting. QED
I understood nothing from this video. On one hand, it makes me kinda mad and a bit sad, but also happy that we have so many people understanding it. Please, never support the de-education of peoples.
The idea is that if there were maps that could not be coloured with four colours, we look at a minimal one. Then we delete some countries. As the new map is smaller than the minimal one that requires more than five colours, it can be coloured with four colours. No we add the countries back and prove that the map can still be coloured with four colours. The complicated part is proving that there is a set of subgraphs so that each graph without crossing lines contains at least one of them. If that is proven, you need to find recolouring algorithms for every one of those subgraphs that work with four colours or less.
You make a good point!
👍 for admitting that you don't understand this stuff.
If everybody were as honest as you there would be no Covidiots, conspiracy theories, Antivaxxers, .... I guess.
Only yesterday I told my daughter that it is not necessarily useless to learn things in school which one will never need again in life - it at least makes one realize that there are things one does not understand but that there ore others who do; so if there is a problem ( like climate change, Covid, ... ), just shut up and let them do their work ( and listen to them ).
For some reason, graph coloring seems much more complicated for me
This is true. My old laptop can confirm...
u deserve more subs and likes
is it same as graph bipartitie problem?
Very very very nice.
Isn't the simplest proof the fact that you can't draw a clique of five or more without edges intersecting?
Very simple, and elegant.
No, you need to consider that there's more countries than just the ones bordering the one that you're colouring right now, some other neighbours of the neighbouring countries might have made that colouring invalid already
@@SabiaSparrow Give me an example.
But how do you prove your statement that we can't draw a clique of 5 or more without edges intersecting?
@@arpitkumar4525 Get out a piece of paper, or open some other drawing app.
First you put one dot anywhere near the middle. Then you draw another dot nearby and connect with a line. The goal here is to add dots, or vertices, which connect to *all other* dots, but their lines *do not* intersect. These first two steps are trivial, and the only "intersection" you could possibly have is if you put the two dots right on top of each other.
Your next task is a third dot, which is also trivially easy. Place the dot anywhere else on the paper that isn't on the line you just drew. Connect all the vertices and now you have a triangle.
When you add the fourth dot, this is your first meaningful decision. You only have two options: you can put the dot inside the triangle, or outside it. These are literally your only options, unless you want to put your dot on one of the other lines or dots you drew, which is automatic failure.
If you put your dot inside the triangle you had, you can easily connect it to all the other dots and still satisfy the requirements. If you put your dot on the outside, it's possible that you can't. You would have to position the dot so that it is essentially extending from a point on the triangle in order for your new dot to connect to the back two vertices. If you do not position this dot correctly, it can't reach the vertex in the back without crossing an existing line.
If you think about what we've done, it is logically impossible to have arrived at any other outcomes. And if you think about it more, both examples we end up with are pretty much the same configuration, but perhaps stretched in certain ways.
The last thing to do is try to add a 5th dot which connects to all the vertices, but does not cross any lines. And here is where we run into a problem. Place the dot anywhere inside the bigger triangle, and it is boxed in and can only reach 3 of the 4 previous vertices. Place the dot outside the large triangle, and although you can reach all the outer vertices, you can never reach the inner vertex without crossing a line.
This truth is absolutely undeniable, and therefore it is a form of proof. If you are looking for something purely mathematical, I don't think anyone in the comments section has any time to entertain you.
Has math solved gerrymandering? Area to circumference ratio
I understood the six colour proof.... but five colours already was very hard for me.
This would make a great project for math students at any age. Ask them, color in this map, so that no neighbors are the same color, and try and use the least amount of colors possible. See who wins.
You raise a good point: While the theorem proves that you can colour any map in four colours, it does not tell you HOW. For a very complicated map you will run into issues, if you you try it by hand. Then you may need some of those complex recolouring algorithms.
@@skyscraperfan or just like ya know, make the kids think a little and use their brains.
@@Emc4421I don't know why you think what the other comment said isn't "using their brain"
Exclaves and enclaves in question:
With enclaves and exclaves the number is not limited, as each country could have an exclave in each other country. Then each country would need a different colour.
so this only applies to maps with "states" that have five or fewer neighbors?
No, the proof uses the fact that every map has *at least one* state with five or fewer neighbours, that doesn't mean higher ones don't exist
Highly recommend Donald Mackenzie's book Mechanizing Proof
How many theorems make a theory? Shapes and Colours make a state?4 points of references=D
What other theorems are proved by computers by now?
Historic counties!
What would a human understandable proof be worth, as in how could the prover's efforts be rewarded? And I don't mean BS such as the accomplishment being reward in itself. I mean financial or livelihood gain.
4:00 But this doesn't account for every possible map I wouldn't think
No, it doesn't work for exclaves. The regions have to be contiguous
Yorkshire is massive!
As a digital cartographer, give me any map and I am making it with four colours
what if a dot has 6 neighbors?
I wonder how many colors you'd need to color a 3D map?
I don't get it. Not all countries share a border with at most 5 neighbours.
That's not necessary, the proof uses the fact that each map has *at least one* such country, it focuses on that country to reduce the map, proving the counterexample false
1:07 Evidence might be that color was expensive to produce at the time. So, it could be a valid reason, and cartographers are more mathematical than the average joe.
great timing to release this story. More AI and learning based methods will be the important in many computational field
Interesting.
what about 3d map from starwars
How many elegant proofs have we missed doing this?
Such as?
Well that is kinda the point we don't know.
The Four Color Theorem, which states that any map can be colored with only four colors without any two adjacent regions sharing the same color, was a longstanding problem in mathematics that was finally solved in 1976 with the use of computers. The problem was initially posed by Francis Guthrie, who wondered if the four-color rule applied to all maps. Mathematicians attempted to solve the problem for decades but couldn't find a proof that satisfied everyone. It wasn't until Kenneth Appel and Wolfgang Haken developed a proof that relied heavily on computers that the problem was finally solved. This sparked a debate about the role of computers in mathematics and what it means to be a mathematician. The proof has wide-ranging applications, from planning wedding seating arrangements to assigning frequencies to radio stations. The problem was originally thought to have come from cartographers, but it was actually posed by mathematicians. The problem can be simplified by converting maps to planar graphs, which are easier to analyze. Mathematicians use graph theory to study relationships between objects, and this helps them analyze the Four Color Theorem. Although the proof is not without controversy, it stands as a testament to the power of computers in mathematics and the innovative thinking of mathematicians.
Wonder if something like that exists for 3d
on second thoughts. some more stuff. Haken died in October last year. his family are also a bunch of geniuses. armin proved some stuff which Pudlak mentions in "proofs as games". the idea of "gameifying" proofs to use human "game play" intuition is interesting. but the actual fact that it works as a strategy is fun. even when it doesnt, which harks back to this problem as a game (see "the map-coloring game" by Bartnicki, Grytczuk, Kierstead and Zhu. as expected, popularised by Gardner) it reveals some great facts about strategy, like Daltonism (colorblindness) might force a player who suggests the game to another to change the game to something similar and yet they can still get a winning stategy that can be back-ported to the original game!!
I've learned about this from Persona 5
take lesotho and separate it in four quarters, all of them will touch each other and will be four colors, now add south africa back and BAM the four color theorem is wrong unless you dont count corners which is fair
The theorem doesn't count corners
If corners are counted, any amount of colours may be necessary because any amount of countries can touch in one point
Uh oh, a problem?!
Is this related to six degrees of Kevin Bacon? Because it feels like it should be...
crazy how this random thought evolved into something that connects the whole world
...
Wait, wait, wait, wait, does this account for exclaves, and enclaves?
No. if you add non-contiguous reasons it's easy to create an example that requires more than n colors for any given n
I’ve created an example where you need 5 colours. When you have to deal with several enclaves. That blows this theory out of the water!
Obviously this requires contiguous reasons. With exclaves it's really easy to make a map that uses as many colors as you like
This theorem would fall apart if two non-neighboring countries decided to build a bridge over a third, causing the map to become three-dimensional.
Sorry to sound crude and dumb but why does colouring of a map matter?? Can't you just colour it whatever you want? Again sorry to sound dumb, i am not really a mathematician.
If two neighboring countries have the same color, you might not see that they're different countries, especially at a distance.
I can solve this Quite easily. Use more colors like maybe 6.
Only 4 colors are required, you did not disprove anything.
I wonder how long it would take to run the proof on modern computers 😂
Can't you have 1 huge country connected to 20 other large countries?
Yeah, but you can't make the 20 countries border each other
@@0106johnny What do you mean you can't? Draw a rectangle, and then draw 20 rectangles 20x smaller than the first, all touching it.
@@anonanon2031Yeah, but the 20 rectangles wont all touch each other, so you can still use four colors to color them.
That is the part I don't understand. Why wouldn't 1 rectangle touch 20 others?@@0106johnny Therefore, requiring you to have 20 colors so no two colors touched...
Mathematicians failed to consider exclaves and overseas territories.
The word map in math doesn't count enclaves or exclaves
My proof (if you can call it that) is simpler: the main stress is on the borders. Every country on a map has either an odd or an even number of bordering countries. An even number only requires 2 extra colours to contrast with the home country, while an odd number requires three extra: so no configuration of a country and its neighbours needs more than 4 total colours to distinguish them from one another. This is true of every such instance in 2-D. Each neighbouring country has exactly the same scenario. Exclaves won’t always work though because of an unviable rigidity in such an extension of the system. So it’s a problem of numbers after all. A neat little piece of history with the computer proof being finally clearly a proof after all, which I had previously doubted.
That only proves it for one country and all its neighbours. Both those countries have neighbours themselves. Every graph with no crossing lines can represent a map. So their are endless possibilities.
and each such country is subject to exactly same constraints and opportunities. I'm not yet convinced I'm wrong, but if you could explain it in simple terms . . .?@@skyscraperfan
@@skyscraperfanso iin that case, you can have canada swallow usa to create The Great Canadian Empire, with X+Y states....whiiiich still follow the topological rule that that other person mentioned.
The 4CT is pro-imperialist, and thus, I reject it, just fyi.
Is it just me or the paint colour he is wearing looks a bit sus
The simplest shape is a triangle which has three neighbors plus itself = four colors needed = more complex shapes may need less but couid never need more.
GraphQL's origin story?
Or make them unique like everyone knows the color of Germany is Gray, Italy is Green, America and France: blue and the UK: red.
When I was a kid I just assumed it was for the same reason that you cannot have more than four shapes each touch each other simultaneously on a 2D plane. Not sure why that would require a complex proof lol.
" cannot have more than four shapes each touch each other simultaneously on a 2D plane"
@@xynyde0 it’s not obvious to me why it wouldn’t be the opposite
This proves that you can colour a country and its neighbouring countries in just 4 colours, but when you go to the neighbours of the neighbours you might run into a conflict with the colours you've already used, and it's not as simple to prove there's no such conflict
The "music" is really annoying.
First
you have indeed been first, however no one asked
About your opinion