The Five Color Theorem (without Kempe chains)
ฝัง
- เผยแพร่เมื่อ 20 มิ.ย. 2024
- Submission for the #SoME2 competition. Most animations were done in manim (www.manim.community/), and the 3d images were rendered using svg3d (github.com/prideout/svg3d).
Proofs:
The degree of a vertex or a face is the number of edge incidences (edges that meet a vertex or face twice are counted twice). Each edge has two vertex incidences and two face incidences, so both the sum of vertex degrees and the sum of face degrees equals 2E.
Eliminating "bad borders" means that each vertex has degree at least 3 (unless there are just two faces). Then, the sum of degrees is at least 3V, and hence 3V ≤ 2E. Plugging that into Euler's formula to eliminate V yields the inequality E ≤ 3F-6 (when F ≥ 3).
You can't have a neighborly map of six countries because you would need 6 choose 2 = 15 borders, but 3(6)-6 = 12. The average degree of the faces is 2E/F ≤ 6 - 12/F, which is less than 6.
Errata:
Whoops, looks like Franklin's paper was actually from 1934, sorry!
![พาแม่บินครั้งแรก..เกือบวูบ! ให้เกาหลีเยียวยาใจ I Korea Ep.1 [Seoul] x อุงเอิง](http://i.ytimg.com/vi/waL3__dEQBU/mqdefault.jpg)
I forgot to mention in the video that the proofs of the claims in the flowchart at 7:56 are sketched out in the video description. Hope this helps!
10:20 it's pretty easy to see that 2 and 4 would work because any chain of 2s and 4s connected to the 2 is isolated by the 1-3 chain.
Considering proofs as algorithms, and vice-versa, is one of my favorite mathematical techniques. It actually has the fancy name of "the Curry-Howard correspondence" and has given rise to many fascinating things which this margin is too small to contain.
A fellow TAOCP enjoyer!
@@aruvi444 I didn't recognize that acronym, but now it is on my to-read list! Thank you for the recommendation.
The Curry-Howard correspondence (aka Propositions-as-Types) is really important to many proof assistants, including the one that the proof of the four color theorem was written in. It lets you treat a proposition P as the type of its proofs, so that a proof p of P has type P. That way, instead of writing "R is the statement that P implies Q" you can write "R is a function that takes in proofs of P and outputs proofs of Q". You could therefore prove the statement "If x + 3 = 5, then x + 4 = 6" by creating a function f of type x + 3 = 5 -> x + 4 = 6 (that is, f is a function that takes in objects (in reality proofs) of type x + 3 = 5 and outputs objects of type x + 4 = 6).
@@osbourn5772 ... which thus makes Modus Ponens just function application. From f : P -> Q and x : P , construct f(x) : Q
(read ":" as "with type", or "which is a proof of")
Cool!
Really wasn't expecting this to be the first video of the channel, looks so professional, nice job. Of course, the great manim helps.
manim is overpowered!
Thank you for the video! I've been working on formalizing the five color theorem in Lean. I'm using the Kainen 1974 paper that you referenced in the video. It was refreshing to see another take on the topic.
We can create a map such that The Greedy Algorithm can use an arbitrary large number of colors.
Let's start with a region in the map. Color it.
This set of regions (only 1) will be a1.
We create another region and place a1 inside it, it has to use the color 2 since it is bordering a1. We call this set of regions a2.
We create another region and place a1 and a2 inside it, it has to use the color 3. We call this set of regions a3.
We can use this process to go arbitrarily large in numbers.
Nice proof! :)
This is a somewhat different question, where you’re forming a map *and* a greedy coloring (from what I can tell) - the OP is asking that, given a map, how many colors can the worst case be
But, your question is also quite fun, and I came up with my own solution :)
You can actually do this recursively, since if you can make a map with n colors, you can put n of them around one region (in such a way that they don’t neighbor each other), reorder the greedy algo such that the pattern is the same but the palette is shifted, and then put them around one region
More rigorously, we can make a map of 1 color by having one region
Then, we can put two of these maps together, and put a region connecting the two (call this region the Capital of the map) and the capital must have color 2 since it borders two regions of color 1
Then, copy this region, and order the greedy algo to swap the colors (it is a fun exercise for the reader to find an ordering that does this) and form a new country that borders the two copies at their Capitals; because we have the original with capital color 2, and a color swapped copy with capital color 1, this capital must be color 3
The true inductive step, now, is to consider a map of this sort with capital color n. We take this map, copy it n times, and reorder the greedy algo to palette swap so that the copies all have different capitals colored 1 through n, and form a new region that borders all of these at their capitals; this region is a new capital that is colored n+1
@@strengthman600 16:45 : "Can you come up with a map and ordering that uses 7 colors? 8 colors? How big does it get?" If you're given a map it is just a matter of looking for regions with k connections and at least one connection with k-1 connection and 2 connections with at least k-2 connections, etc, etc and each of the k-a connections to have at least a k-a-1 connection and so on in a way that they don't require a connection to be 2 different colors. If you're looking for how big can it get for any map with at most m regions I have a feeling that there is gonna be a somewhat complicated recursion base plus some form of squeezing to get the last couple of colors in. The sequence being 1,2,3,4,6,8,10,etc.
@@luminica_ yeah no I realized after I had left the comment that I was the one who misinterpreted; I was thinking about how to solve the other problem and realized how utterly challenging that would be, then went back and figured you were right
Either way, an interesting follow up to this one is to see how bad the greedy algo can be in terms of the size of the graph (treating the greedy algo as an approximation of the NP-hard graph coloring problem)
It’s a common result to show that the greedy algo can never be as bad as the degree of its largest vertex (and a clever choice of ordering can reduce that worst case by 1) but that’s for general graphs, for planar ones specifically I wonder if it would be better in general
Feedback:
This video gives really good introduction to map coloring algorithm from the point of view of computer science.
Further reading:
You may be interested in reading some more materials in graph theory topics, for example:
1) R. J. Wilson, Introduction to Graph Theory;
2) D. B. West, Introduction to Graph Theory; J. Clark; and
3) D. A. Holtan, A first look at graph theory.
These may prove some solid graph theory background for related computer science topics like TSP or Chinese Postman Problem, and also some mathematical idea behind interesting algorithms like Dijkstra algorithm and Kruskal algorithm.
Great video! I hoped to see something like this for a while because the topic lends itself nicely to an animated video, and you did an awesome job with it.
Very good video. Your explanations break down the concepts enough for most people to understand them but you still keep them short and concise. Adittionally your examples and visuals are extremely helpful.
Bloody brilliant! New sub here. I'll be seeing you when you hit 100k and beyond (and well deserved it will be). Bravo!
Interesting, two nice proofs of the 5 color theorem I didn't know! We actually learned a third proof that found minors K5 or K3,3 when more colours are needed, and as these can't be drawn on the sphere, it means you never need more colours on the sphere.
for the 3rd challenge, you can need infinitely high number of colors. we can recursively create a map that needs n colors by appending n-1 smaller maps (each needing a different number of colors) to a new region. If we only append to the top edge, we get an exposed edge to the highest color at the bottom, which we can use to connect to the following maps. at 2^(n-1) regions for n colors. i'ts not optimal in the number of boxes, but we know it exists. coloring this map top down will require an extra color. funny part is that this construction makes trees which should be 2 colorable
e.g.
1: trivial
1
2: also trivial, but using the recursive function: add the 1 map created above to the top of a new region
1
2
3: add the 2 maps above, side by side but not touching to the top of a new region
1
2 1
333
4: add the 3 above to a new region
1
2 1 1
333 2 1
4444444
...
One of the best videos I've ever seen. Bravo, monsieur! 👍
Great video. It was really interesting, well crafted, and you have a pleasant voice!
Great video for 1m+ TH-cam channel. Can't believe you're just starting out. Superb.
I'm not sure I understood most of it, but the graphics really helped visualise what you were talking about. I've definitely much to learn still
Such a great video! Congrats!
I can't believe this is your first video on the channel with this quality. Keep it up
dude! This is a dope video
well done, very pog :)
Great effort, keep up the good work.
I never knew about color theorem before this video. Know, I do know about color theorem, and have a decent understanding of it as well. Gained yourself a subscriber!
Great video!
Great video, understood suprisingly much from, even though I've never met such problem before
Excellent video
This is great!
cool video. was able to learn a lot of new things
This is cool kinda reminds me of 3blue1browns style voice over (very kind and wanting to help you learn) which made it a very fun watch
And I definitely had a lot of
Whoa that's interesting
Type moments
I can't wait to see what u make next
Good job for a first video
I'm glad to have seen this video. I've been reading literature on register allocation by compilers, which is a practical use of graph coloring (variables are countries, registers are colors and boundaries are calculated based on when are variables used or "alive"). I'd like to know when your algorithm decides to merge, since in the practical case this decision might assume some property of variables.
This is not relevant to register allocation since you can create a neighborly map of any arbitrary size.
The merge operation is used for faces with exactly 5 neighbors.
Instinctively, I'd conject that greedy colouring can be boundlessly bad, where, for any positive integer, you can always construct a map and an order in which you do the greedy colouring and end up with using no less colours than the given integer.
Yep, just use the set theoretic definition of the natural numbers, replacing sets with regions and coloring inside out. Since the outermost region directly contains regions colored 1,...,n-1 it must be colored n
beautifully phrased
Five color theorem proof : the 4 color version is prooven, so if i add a 5th one it's still true lmao
Anyways, good video !
Definitely a valid proof!
Very neat!
This might be the first English video that I had to watch with subtitles turned on, because I couldn't understand a word out of this muttering :q
Nice graphics!
It should be noted that these theories do presume some ground rules for national borders that don't really apply to the real world. Most notably it presumes fully contiguous borders.
Allowing for divided territories, like the US with Alaska or the holdings of HRE princes, breaks the limits of common borders.
One question I'm very much left with is why does the merging proof not also work as a proof of the 4 colour thereom? Where does it break down?
Also some general feedback on the video:
Your presentation is great but the content seems a bit lacking. (what I mean with this is that the second half of the video lacks a bit in how much is actually explained. You mostly just give results instead of GRADUALLY going further into the topic. )
@Erin van der kamp In order to get down to four colors, you would need to have two color repeats among the five neighbors instead of just one. In general, it's not possible to merge three neighbors with the central country without having some pair that border each other. If you look at the example at 10:36, one simply can't even pick three neighbors where no two are "consecutive" along the border. The Kempe chain argument is a little bit more powerful in the sense that it can be applied more than once to the same country's neighbors (and this is what Kempe himself tried to do), but there is an annoying subtlety (see Sipka, "Alfred Bray Kempe's 'Proof' of the Four-Color Theorem") that can't be easily fixed.
I'd love to talk at great length about maps on higher-genus surfaces, but it wasn't the central focus of the video and I was already feeling that the video was getting too long. It was meant to be more like a "future exploration" kind of section. Sorry it wasn't detailed as you (or I) would like!
Our maths lecturer pranked us by using this approach to “prove” the 4 colour theorem. Of course, we knew it must be flawed, as the theorem has only recently been proven using thousands of pages of computer output. I can’t remember the detail, it might come back to me as I watch the video, but if your node with the least neighbours has 5 neighbours, recolouring one chain messes up the other chain. I’ll try and be clearer after watching!
This explains the flaw better than I can th-cam.com/video/adZZv4eEPs8/w-d-xo.html
BTW, there is a great paper discussing the minutiae about what types of countries are allowed and what counts as "sharing a border." The four-color theorem is often described in terms of political maps, but the only condition usually imposed is that all the territories in the map are contiguous (i.e. path-connected), and that two territories "border each other" iff they share an uncountable number of points (e.g. an entire line segment or curve). If we want to be precise, we need a stronger condition. It is not sufficient that our territories are bounded by Jordan curves. These boundaries need additional properties such as being rectifiable for the four-color theorem to be true.
I'm having a hell of a time trying to find an old pdf I used to reference to make this point. I'm sure it's still out there. The idea is that you could make four (or any finite number of) territories share a single line segment as a boundary by making their boundaries infinitely long. They essentially get alternating rectangles of decreasing thickness closer and closer to the shared boundary, so that every point in the line segment is a limit point of every territory. Each territory is path-connected in the usual topology of R², yet all _n_ of them share a common border. Avoiding this sort of edge case requires a more careful formulation in what shape the territories may take, e.g. limiting them to having rectifiable boundaries. This might seem unsatisfactory though, since real territories do not have rectifiable boundaries in the mathematically ideal case. Basically, we just want the connectivity graph to be planar, but exactly what that means in terms of our map is more complicated than one might expect.
I believe the paper you're referring to is Hudson, "Four Colors Do Not Suffice"
@@Timothy-Sun Awesome, thanks!
nice video
The answer to challenge 2 is yes:
Take any optimal coloring C. First greedy color every region that has a 1 in C. Since they have the same color in the optimal coloring, they none of them can be neighbors, so they're each colored 1 in the greedy coloring. Next color every region that has a 2 in C. Since none of them are neighbors and the largest color we've used is 1, each receives color at most 2. By induction, each region receives color less than or equal to its color in C, so the greedy coloring uses at most as many colors as optimal coloring C, i.e. is optimal
For the last challenge:
You can get arbitrarily bad with just trees:
Let T_0 be a single vertex. Let T_n be a rooted tree with T_0 .. T_{n-1} as its subtrees. Color the leaves in reverse depth first search order.
This uses 2^n vertices to force n+1 colors, and I believe it's the optimal number for trees. The follow-up challenge is, how many vertices do we need using arbitrary planar graphs? Can we get better than O(2^n)?
We can get O(2^(n/1.5)) using a hierarchy of 3-neighborly maps (say circles divided into 3 segments). To iterate, we embed a copy of each of the previous maps in each segment of the circle, forcing them to use 3 new colors (coloring inside-out). We quadruple the number of regions (since deleting the 3 copies of the previous map reduces the new map to the previous one) to add three colors, giving O(4^(n/3))=O(2^(n/1.5))
Edit: actually I think we only need to embed the smaller maps into 2 of the 3 segments, and they can each "share" 2 out of 3 colors with the 3rd segment by poking part way across what would otherwise be the boundary between the segments. So we'd only need to triple the number of regions at each iteration, giving O(3^(n/3))=O(2^(n*lg(3)/3))~O(2^(0.53n)) rather than O(2^(0.67n))
Awesome video! What tools you used to create it?
At 7:38 E
You're right that the dual of your construction violates the inequality, and this is essentially the second example in the "Bad Borders" section that comes before the timestamp. Maybe I should've worded it differently, but not having "bad borders" is the "ordinariness condition" you're looking for (see the video description for the proof).
The way I read about the Four Color Theorem was an inversion of it (not sure if this is the right term, but w/e). When will you absolutely positively need a fifth color? If you have a cluster of five countries that all border all other countries. As it turns out, this is impossible on a simple flat plane (I.e., not a torus or something like that.
With one country, there is of course nothing else to border. With two countries, you just get any random border. Neither of these are all that relevant, but they still have to be named for the sake of logical progression.
With three countries all bordering one another, they can appear on a map in several ways, but their way of touching can always be viewed as a triangle, with each point of the triangle being a county and each edge of the country being a border.
What about four countries all touching one another? Well, you'll have to take a set of three countries first. Then you can place the fourth country either in the middle, completely surrounded by the three other countries (and therefore unable to touch any other country as long as the three other countries all touch one another). Or you can place it on the outer edge, touching all three other countries from the outside. Note that these two are functionally identical, because in the last case, you'll just end up with another country completely surrounded instead. Either way, this can be seen as a large triangle consisting of three smaller triangles -- the center point being the fourth country.
And now we look at five countries instead. Take the set of four countries mentioned above. Is there any way in which you can introduce a fifth country that touches all four other countries, whilst also keeping all currently set borders intact? No; any attempt at doing so will disrupt at least one border. This can be easily proven by taking the previous triangle consisting of three triangles, adding a fifth point anywhere inside or outside the shape, then trying to draw a line to all four existing points without crossing any of the existing lines. You can't do it. Therefore, sets of five countries that all border all other countries of that set do not exist. Therefore, you never need five colors; you will always be able to reach four colors with enough shuffling.
The actual proof of the four color theorem is a bit more elaborate than that. Because you need to also consider how multiple clusters of countries interact with each other.
Cool video. I understood why the Kempe chain argument works, but the merging not so much 😅 why it never needs the sixth color?
how would coloring work with adjacent 3d objects? how many colors would you need minimum?
There’s no bound possible. You can come up with an arrangement of any number of objects that all touch each other in 3D, it’s not even particularly hard (start with n cubes, extend a tube from cube 1 to all other cubes, from cube 2 to all other ones except 1 and so on, so that none of the tubes touch. the ambient space is the final region).
Liked. Did you teach at Emory?
Sometimes I wonder if the four-color-theorem would become a five-color-theorem in 3d. I noticed that the prototypical neighborly map of 4 countries is essentially a flattened tetrahedron, or 3-simplex, which is the largest simplex that can be constructed in 2d without edge self-intersection, and remembered that the 4-simplex would represent a neighbory map of 5 3d countries... or, I suppose, at this point it would be more accurate to call it a "cell network" rather than "map". maybe even a "tissue"? Like, because biological tissue is made of cells?
At the same time, though, I remembered watching a numberphile video about how it's possible to construct a 5-simplex in 3d without any of the edges intersecting one another (th-cam.com/video/2s4TqVAbfz4/w-d-xo.html), but something about it FEELS more intersecty than a 3d drawing of a 5-simplex, such that i'm not sure you could make a neighborly cell network by creating cells around the vertices of a 3d projection of a 5-simplex, and I'm really not sure how to explain why.
EDIT: after looking more closely, god the 5-simplex in 3d has so many intersecting faces
Cut a 1xnxn cuboid into n 1x1xn stick-shaped regions, each with their own color. Make a copy, rotate it 90 degrees and stack it on top of the original, forming a 2xnxn cuboid; merge regions of the same color. Then every region touches every other region.
@@columbus8myhw ...Well that feels like it should have been obvious. At least it's nice to hear a problem I had been thinking about isn't just a total mystery, LMAO
@@GarryDumblowski I only was able to answer it so quickly now because I, too, spent a lot of time wondering about it… just, a long time ago
your illustrations of maps as voronoi cells made me wonder: can we take any arbitrary map and make a voronoi cell diagram that preserves its structure/dual graph? do we know this?
OOOOOOOOOH I see
there is another pretty notable restriction present here that isn't for actual countries- colour maps do not allow for enclaves/exclaves. if you do allow for exclaves, it's pretty easy to make a map that breaks the four (or five or six) colour theorem
Very nice. Regarding "efficiency" 13:06 are people running these algorithms for real, or is that just a way to do a proof?
The first two papers I flash at 2:04 are actually algorithms papers. Don't know if anyone has implemented them for anything "useful" though...
Couldn't you do the merging colouring from a top down perspective and start out as 1 supermerged face and work your way from down there?
Luminica already gave an iterative process to create maps that the greedy algorithm needs an arbitrary large number of colors to color, and I admit his solution is nicer than mine, but here's what I was thinking about:
I'll prove there exists a map the greedy algorithm uses n colors for by strong induction.
I want the greedy algorithm to use n colors. As long as it does that, I'm fine, so I'll assume it's the last region colored.
My proposition for n is "There exists a map (regions+ordering) which the greedy algorithm requires n colors for and the region colored n borders the outside."
Initialization: It is true for n=1.
Heredity: Assume it is true for all i between 1 and n-1. Then, to build a map for n, do as follows:
You have a region; that region needs n-1 differently colored neighbors. You have maps that do that and have a border of an i-colored region on its border, so you can attach them to the sizes of our region. You can reshape them so they don't touch each other and leave some empty border on our central region. Thus, you have constructed your map for n.
can someone explain why you can't stretch colour 3 or colour 5 over colour 4 to remove it entirely from the Klein bottle case?
I've noticed that x=(x²+6chi)/7 (weighted average) where x is the minimum number of colours needed to colour any map on a surface (except a sphere or Klein bottle) with the Euler characteristic chi
Correction: x can be larger than the number of colours, but less than by 1
So wait Ringel-Youngs doesn't apply to Klein bottles or spheres and that's the end of that? Do people have any idea why?
"How were all these neighborly maps constructed?" (meaning one of the main reasons we watched this).. Let's save that for another time he says... Otherwise, nice video.
This likely makes the question much more complicated, but I think it is an interesting question given history. How do non-contiguous borders affect this theorem? If we were to apply this to something like the Holy Roman Empire, what are the minimum colors needed?
I don't know if this is exactly the scenario you're talking about, but there is a variation known as the Heawood empire problem, where countries are allowed to have more than one region.
More plz
What about edge cases such as Swaziland in south Africa say Swaziland and or parts of South Africa break into 5 independent countries all sharing a boarder, while still being surrounded by South Africa. This theorem breaks down with fully Surrounded countries.
i always think of this problem considering the exterior as a color. you can always use at leats 2 colors for all the faces bordering the map, 1 color more for the exterior face, and 1 more for the case of an odd numer of faces. For me thats the proof of 4 colors. the interior must have a solution somehow but the border is enough to show that you need at least 4 colours and 3 is impossible.
Not to sound rude, but how is this accomplishing anything new? The existence of a 4 faces all bordering each other situation, as shown in the video, is enough to proof that 3 will not always be enough. The real problem is showing that you never need 5.
The merge operation corresponds to an edge merger, right? So that you get a graph minor of what you started with? That smells a little like it should connect up to Kuratowski's theorem...
Yes, the dual of the merge operation is an edge contraction.
What about exclaves?
Wait how do you have only 320 subs?
... Oh this is the first video... Call it 321 subs now
Please take this as constructive criticism - I found the video informative and interesting. However, as a native British English speaker (64 years) I really struggled with your accent - too many words ran into the next and became rather indistinct. I am afraid I had to resort to enabling the subtitles. The downside was that reading those was then a distraction from the (good) graphical content. This was unusual - I have very few problems with accents in general, whether American, European or Asian, since we in the UK are exposed to so many. Anyway, please don't let that detract from the fact that I liked the video.
No puedes probar que necesiten sólo esos colores, los países pueden tener territorios esparcidos, puede existir una situación en la que todos los países sean vecinos de todos, así que harían falta tantos colores como países haya.
Does the addition of exclaves change anything? That is, if some shapes are linked and must share a color, do you still need five colors minimum?
If exclaves are allowed without restriction, isn't it easy to make a map that requires an arbitrarily large number of colors, by having every country surrounded by exclaves of every other country?
Its simple, you uhh, you put it on a torus
10:18 should be 4 and 5 right?
2 and 4 work because there is no way that a chain connects the two of them. The 1 and 3 chain blocks any path out from the 2. The reason 4 and 5 don't work is because they're already touching, so they can't be turned to the same number.
It's really hard to tell the difference between some of those colors. I can only imagine what a red-green colorblind person is seeing here.
Try to speak more clearly in the future, great video but I had trouble hearing what you were saying in some spots
Can't the merging proof be modified to prove the 4 color theorem? You just need to allow multiple overlapping merges on the same original map. Also... why can't we just search a map for those positions with the highest number of neighbors and color from there? If the positions with most neighbors have the smallest color number, we should get an optimal coloring.
So you have a region X with 5 neighbors - say (A,B,C,D,E) in order - and you decide to merge (A,X,C) into a single region Y. But is this legal? What if A shares a border with C somewhere else? Now Y has a self-border in a bad way, and there is no legal coloring. If you do give Y a color, then when we get to the point of putting X back in, A and C will be the same color and oops. Okay, so maybe (A,X,C) was not a good merge because A borders with C. Surely there's some pair (A,C), (B,D), (C,E), (D,A) or (E,B) which will do? Well, yes. In fact, either (A,C) or (B,D) will do. But you need the Jordan curve theorem to prove this. Unfortunately, your proof does not gain you as much as you might have hoped for.
At 10:48 I mentioned that we specifically choose two neighbors that don't border each other, which follows from the "no neighborly map on 6 countries" fact from earlier. Generally I prefer using combinatorial results (like how most texts will prove nonplanarity of K_5 and K_{3,3} using Euler's formula and girth arguments). Though one could say that anything derived from Euler's formula ultimately comes from the Jordan curve theorem...
@@Timothy-Sun There's a whole history of people making the mistake that I assumed you were making, so I jumped to conclusions, and I apologise. After carefully rewatching, you are correct. This is a very valuable simplification of the usual proof.
@@ipudisciple No worries! In the future I'm going to try to convey more information visually -- it's really easy to miss a sentence here and there when just listening.
There's not much explained here at all. A bit of a head scratcher. I'm sure it's going to be better next time, the presentation style is very good.
I disagree; I felt the video had just the right amount of detail to keep it interesting and present the idea of each topic. If you want to know the details you would for sure have to pause and think a bit, but that is often the case in mathematics. It's actually amazing that so much ground was covered in such a short video. And I do totally agree that the animation style was wonderful!!!
I also disagree. This video adequately presents a proof of the Five-Color Theorem both with and without Kempe chains. There might be a bit of a learning curve at some points: I think the most obvious jump was when he introduces an inequality whose derivation is left to the reader, then leaves you with two results from that inequality whose derivation is also left to the reader - but they both turn out to be true of course. You could pause to ponder that if youre curious. Another jump was mentioning the Jordan-curve theorem, but he lampshades it a bit by saying that yeah it is complicated and not fit for this short video format.
Are convex polygons allowed as borders? If so, you can make your map NEED as many colors as you want it to without greedy colouring or crooked lines
Some countries (Azerbaijan for instance) are discontinuous. If we want to color each of the country's parts the same, we might need more than 4 colors.
it's not that hard to prove that you can color a map with only 4 colors.
in fact, the proof shown on the video that, sometimes, we need 4 colors also proves that it's impossible to have 5 sections that all are connected to all the others.
no matter where you try to add a 5th section, it will be isolated from one of the 4 sections already on the map (or will cut the connection between two of the existing sections allowing both to become the same color)
why?
if the new section is partly splitting borders, this new section will only have 2 neighbours our of the 4 existing sections so it can be colored using one of the other two.
if the new section is replacing a vertex, the new section will only have 3 neighbours so it can be colored using the 4th color (the one used by the non-neighbour)
if the new section is fully splitting borders, the new section is separating two previously neighbouring sections so we can recolor one of them so both share the same color.
no matter what you do, there will be, at least, one free color or we will be able to recolor a previous section since it lost one of its previous neighbours.
It's not obvious that this process is bound to terminate for every map.
@@rosiefay7283 it is. you can begin building from 4 sections recursively. no matter where you put the fifth section, you won't need a fifth color because of the reasons I gave. now pick the sections that will be in contact with a new sixth section and the same will happen.
you can always add, locally, a new section without needing to add a fifth color. and the rest of the map is already proven, on the previous step, that it can be colored with only 4 colors.
It's easy to prove the 5 color theorum. Look:
Given: the 4 color theorum is true.
Therefore: the 5 color theorum is also true
As a non-native speaker of English, I found some words difficult to hear because your articulation is a bit sloppy sometimes... Example:
0:29 "E[v]en the non-computer prets(?) of the proof are pretty events(?). so [that(?)] these class(?) will sell(?) for weaker results"
Consider watching with subtitles -- that sentence annoyed me in particular, so much that it got me to look into the subtitles feature in the first place. (Unfortunately I didn't have time to rerecord the audio for the contest I submitted this video to)
@@Timothy-Sun Thanks, the subtitles help a lot!
Q: How bad can a Coloring Algorithm get?
A: Arbitrarily bad; Select n colors, where n is the number of faces to color, then for each face chosen, use the "smallest number" color not already used.
I will disagree with this to the day you stop using "country"
Here's a nice false proof of the 4-color theorem also using just maps: superliminal.com/4color/ The challenge is simply to find the flaw.
please read @4shokunin !
Great video!