Solving Math's Map Coloring Problem Using Graph Theory 

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.

😂

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?

The VFX is absolutely high-tier!

Music and audio too!

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.

No they are not, one of the joints was wrongly drawn.

Is that true?

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

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

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.

❤

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 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.

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.

It does not work on enclaves in some cases, because in math the term "map" does not have exclaces

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.

It doesn't.

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.

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

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

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.

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

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"

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?

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.

No, it doesn't work for exclaves. The regions have to be contiguous

Such as?

Well that is kinda the point we don't know.

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 ).

...

No. if you add non-contiguous reasons it's easy to create an example that requires more than n colors for any given n

Only 4 colors are required, you did not disprove anything.

The word map in math doesn't count enclaves or exclaves

Obviously this requires contiguous reasons. With exclaves it's really easy to make a map that uses as many colors as you like

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...

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

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.

If two neighboring countries have the same color, you might not see that they're different countries, especially at a distance.

You misunderstand what the term map means exactly in mathematics

@@Schnoz42069 I don't care what the teem map means in math

@@samsonsoturian6013 Hence why you think there is an assumption when there is none

@@Schnoz42069 then what does this problem have to do with actual maps?

@@samsonsoturian6013 it has to do with mathematical maps

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