The Four Color Theorem - What Counts as a Proof?
ฝัง
- เผยแพร่เมื่อ 19 ส.ค. 2018
- Train your problem solving skills today with SkillShare:
skl.sh/upandatom3
Check out the video we did over on Willie's Channel!
• Why All Maps are Lying...
Subscribe to Willie's Channel KhAnubis!
/ tobirates
The Four Color Map Theorem and why it was one of the most controversial mathematical proofs.
This video was co-written by my super smart hubby Simon Mackenzie.
Hi! I'm Jade. Subscribe to Up and Atom for new physics, math and computer science videos every two weeks!
SUBSCRIBE TO UP AND ATOM / upandatom
Visit the Up and Atom Store
store.nebula.app/collections/...
*Follow me: @upndatom
TWITTER: upndatom?lang=en
INSTAGRAM: / upndatom
Check out this PlayList for a taste of the channel:
• Popular Uploads
A big thank you to my AMAZING PATRONS!
Paul Kendra, Harsh Tank, Alan McNea, Daniel Tan-Holmes, Simon Mackenzie, Andrew Pann, Anne Tan, Joe Court, Adam Thornton, Ayan Doss, Marc Watkins, Sung-Ho Lee, Todd Loreman, David, Susan Jones, Airye, Drew Davis, Rob Harris, Dennis Haupt, David M., Ammaar Esmailjee, M.H. Beals, Doug Cowles, Stephen Veitch, Renato Pereira, Simon Dargaville, Noah McCann, Robert Frieske, Magesh.
If you'd like to consider supporting Up and Atom, head over to my Patreon page :)
/ upandatom
For a one time donation, head over to my PayPal :)
www.paypal.me/upandatomshows
Other videos you might like:
What is the Schrödinger Equation, Exactly? • What is The Schrödinge...
What is a Singularity, Exactly? • What is a Singularity,...
Y CN U R34D DIS? • Intro to Information T...
Sources
projecteuclid.org/download/pd...
Music
www.epidemicsound.com/ - วิทยาศาสตร์และเทคโนโลยี
![MOBYE - มีใจทำไมไม่จีบ (ASAP) [Official MV]](http://i.ytimg.com/vi/dCOdz92FU18/mqdefault.jpg)
Hi guys! So recently a lot of you voted that you would like more in-depth videos, so I made an 18 minute long video! Let me know what you thought and if you would like this level of depth in future videos :)
Also don't forget to check out the video we did over on Willie's channel KhAnubis! th-cam.com/video/jwQlULjESTs/w-d-xo.html
Up and Atom absolutely brilliant video.
they're fascinating!
I could hear you speak all day long
I like it in depth. Now i feel to know enough about it, to understand it on the basics. Thank you.
Hi Jade!!! I'm a high school girl who loves science. I've been following other channels too, but your channel is the best. I love your content, especially because you talk about physics and computer science, my favourite topics and you explain perfectly.
I also like the fact that you see and reply to the comments. I really appreciate your effort❤. Oh, and this video was enough in depth, I really enjoyed it. Thanks😊
The biggest number of sheep you can count before falling asleep is a baa-jillion.
Impossible. Sleep is immediately induced upon reaching a baa-jillion.
Good one. 😄
'badump-bump'
You know what’s hilarious? Yesterday in my discrete math class I gave up on understanding proof by induction and then I failed my exam. And now she just made it all make sense to me. This is a great video, wish I could’ve watched it yesterday 😅
And I love this format of videos! You’re making quality stuff I’d expect from channels like Physics girl or PBS Infinite Series (RIP). Keep it up, your channel can grow as big as theirs 😁
Daniel Kunigan good thing you understand induction now because it's used so many times in other math courses, especially real analysis lol
How the hell is a dot and a line supposed to represent the actual border of a country or county??? Have fun with Michigan.
@@ChrisFerguson-zm4gtNot the only video taking this line.
@@ChrisFerguson-zm4gt Michigan is bordered by Wisconsin, Indiana, and Ohio, so it can be represented by a dot connected by lines to three other dots (which represent those three other states).
@@Ramanuj_Sarkar my comment was almost half a year ago. Im not going to rewqtch the video or correct rewqtch. Im lazy like that. So i have no idea what ur talking about.
4:08 when portugal's been hitting the gym too hard :)
Yeah, I had a feeling people would notice.
Proof by brute force.
Cory Mck thats why i suspect most found it "intellectually unfulfilling". most of these proofs are "elegant" in some sense and can be applied purely using the logic of the proof without having to check all variable cases individually. but for the four color proof it had the requirement of checking each and all possible base variances for if it would hold (i.e. brute forced a solution) and making it essentially "solving only through empirical testing and not by pure logical thought".
greenfox001 Right, just to clarify, that is actually the name of the type of algorithm used. A brute-force Search or exhaustive search in Computer Science is "a very general problem-solving technique and algorithmic paradigm that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement."
Cory Mck oh i know, im a senior studying comp sci currently. I was trying to tie this fact to the part of the video in where this method’s result left so many begrudgingly accepting it (while also trying to write for anyone else who reads these comments). While it indeed was a solution as a proof, it being solved by testing each case individually was the opposite of the elegance that solving it with a pure conceptual and logical proof would provide to mathematicians.
This is how I feel about it too. We've come to a point where we've unknowingly stumbled into a problem where the set of information to consider is so incredibly large and so varied that's not as simple as just individually comparing elements against each other. What we needed, and ended up with, was proof via exhaustion. While some people may not consider that "intellectually fulfilling", it still gives us valuable information about how the universe operates. Imagine a cell in a living organism optimizing for the most energy saving conditions, generating the least diverse set of interlocking modules as possible while maintaining no consistency across its face. This proof shows us that a cell could do this while producing only 4 structures. That's incredible.
Good point avfusion. The other thing is that even if a computer exhausts trillions of possibilities to reveal a proof, it might reveal something about nature or math truth via the computer program itself and it’s analysis. A simple undiscovered CS principle could predict the math result. Halting problem only applies to totality of programs.
You deserve a *_Bajillion Jillion+1_* subs
BOI OH BOI This woman needs to meet Quiteshallow. You would make a funny couple ;3.
nhi degi
How many South-Americans does it take to screw a lightbulb?
A Brazilian.
Badum tss.
@@Onnozelfilmpje i will forever hate you for making me laugh at that
@@PedroHernandez-uy3pi same
Fantastic video! One of, if not your best to date. I think this was a great level of depth to cover the topic at, although I'd be happy with stuff even more mathematically rigorous/challenging.
The video length was great too. Even though it was pretty long, it was engaging and informative the entire time. It never felt like it dragged or anything. Keep up the great content, can't wait to see what you come up with next!
Your in-depth videos are the Sunshine in which our attentions spans grow! I appreciate your gentle spirit. Thank you.
Long form is the new black, I mean, the new short form, I mean, it's good. I started a podcast awhile ago and my co-host wanted to do episodes of about an hour, and I felt it was too long, but then I found that the podcasts I enjoyed listening to ranged from 45 min to 2.5 hrs. People are far more curious than industrialized society gave them credit for...
You forgot Liechtenstein, Monaco, Andorra, Vatican City and San Marino in your map. You better hope KhAnubis won't see this👀
Oh I saw it. I saw it, alright.
Haha what can I say I’m from Australia
Up and Atom I'm from Austria that's pretty much the same💁
Canada… one color required… snow white!
You mean you are part of the great hoax. We now know that Australia doesn't exist.
Definitely love the more in depth video and I liked the length. It always feels easier to watch a video (or 2) that's around 20 minutes than one that's around 30-40 minutes.
I was an undergraduate at the University of Illinois at Urbana-Champaign in the early 1980's. I had both Prof Appel and Prof Haken as instructors. One year, on an early Wednesday morning, the day before Thanksgiving, 80% of the class had already departed for the holiday. Looking around the near empty classroom, I asked Prof Haken if he wouldn't rather talk us through his and Prof Appel's proof on the 4-Color Problem. He did so. He too mentioned that many refused to accept the proof due to expansive use of a computer. It was a memorable lecture...
Excellent explanation of five color proof! Awesome job! For some reason, the four color theorem and Fermat's last theorem always fascinated me growing up.
Level of depth was great! And it's much better suited to your narrative style and humor. Really liked how you drew out from the particular problem some general ideas about math - 3 kinds of proof techniques, the place of computers in mathematics, representation of same information in different forms. Cheers!
This is interesting I never knew about it! Thanks for this video!
And also thanks for making in-depth videos!
Awesomeness! Love what you do! Thank You again! You make Science Fun and Approachable. Share you to other's when I run into blocks in explaination and understanding. You help a great deal in these endeavors. Bless You!
Excellent video! I enjoyed the history and the breakdown of the proof methods used to solve the 5 color proof. I thought this video was just right, more depth but still only about 20 minutes. Great job!
interestingly, there was an analagous story in the field of close packing (of uniform spheres).
sadly, when thomas hales was able to prove the long-standing kepler conjecture by the `brute force' of computation, the maths community refused to celebrate his achievement
totally ! What is so interesting about this, is that thomas Hales even went to the trouble of making a formal proof of his theorem. (Flyspeck project). There are also formal proofs of the 4 colour theorem.
What a great video this was. This really gave me an in depth information without confusing me. Your videos are great and and catch my eye of interest. Keep making such excellent videos and best of luck
love this level of depth! maybe not for every vid but a super-vid every so often would be awesome :)
Concerning in depth videos: I've been somewhat intellectually deprived since PBS cancelled the Infinite Series channel, so I was delighted to see a nice simple looking problem that has confounded mathematicians for a long time stripped down. I'm guessing you don't have quite the resources PBS commands, but I like your plucky attitude
Thanks! Yeah that's such a shame infinite series was cancelled. Do you know why? I thought it was a really successful channel so I was shocked when it was cancelled
I'm just puzzled that they cancelled a series called 'Infinite'.
@@upandatom No clue. Certainly had plenty of subscribers though not quite as many as SpaceTime. I relish in some mental gymnastics for a multitude of purpouses, but it's certainly not everyone's cup of tea, and the Infinite Series had some real puzzlers (though often easier to follow than Numberphile). And PBS also had no trouble finding presenters with a pleasing appearance for the channel (also nice voices). Unlike Eons or SpaceTime, the Infinite Series seemed to require only very basic CGI, and as this is often a major cost factor for any visual medium, I can't imagine that cost was much of a reason.
Infinte Seris was cancelled ? That used to be the best mathematical chanel on the whole internet !
@@pablodenapoli1667 yeah it was a real shocker
Your videos are awesome you deserve more recognition
The video was interacting and had a good level of depth. I listened to it 5 times and tried to do supporting research at the same time and develop my own understanding of the original proof! I'm very picky in understanding math proofs in their true depth since I'm a math major myself. THANKS for the video
I have always had my suspicion about this theorem because I have done a great many art paintings using just four colors, my shapes in them are all orthogonal. Thanks for introducing me to Euler’s name and the problem and solution.
I really enjoy your video. Your explanation make me understand more about the challenges of the four colours theorem. Please keep it up 😄
This video is fantastic, I'm really glad you weren't afraid to talk about all the juicy details. I don't hate many things, but when I watch a science or math channel that says "no let's not get bogged down in the details", it makes me furious! Again, thanks for going into a lot more depth for your curious viewers, I'm glad this is a trend for many math and science channels.
Sincerely,
A math major
I'm crying for the shape that you gave to spain xDDD
Sicily didn't even get a shape :-(
I was distracted by how she looks absolutely sloshed in the animation lol
Love your channel you made complicated things fun
I sometimes do colourings for recovery/self-care and I noticed this rule in a recent one that had an asymmetric interlocking geometric backdrop.
Great video explaining this proof. One additional step that I would show is explain why every map can be represented as a planar graph. I was able to figure this out on my own but I also took graph theory in college and I don't know if it would be as easy for everyone else.
So in depth that I skipped your five color theorem proof because I always like to figure out proofs for myself before seeing other proofs! :)
In other words, you definitely went in depth, and I like it!
I love how this presentation makes me smile and puzzle both at the same time!
I love these cute animations 😊
The way you use humour to stay engaged is really awesome. May the force be with you!
Love your teaching. Can't keep away. Perfect in every respect. You are a model of scholastic ideals.
Great video. In depth is good. You have such a great way of explaining things that more is definitely better.
The one thing I don’t get about the 4 color proof is the “reduction” of the 5 color graphs. By what right can we just start removing vertices? I’ll rewatch a few times to see what I missed, but wouldn’t removing a vertices make it a new graph and therefore any proof is inapplicable to the original graph? It’s why we can’t just say oh well pi is too hard so I’m just going to use 3 for everything instead...
I've never seen a ad on this channel....and i have watched every single video of this channel.
I love the four color theorem! Thanks for making this video
Wonderful channel. Gonna binge it and prematurely subscribe :-)
Only question: What's with the nervously jiggly-wiggling graph(ics)?!
What a polished, well structured video! So interesting and beautifully presented. This must have taken a lot of work to produce. Watch out, numberphile!
Loved the 4CT & its detail. I've followed you for some time but just discovered this...4 years late. Thank you.
Still showing my students this! Thanks from 2021,
I think both sides of the discussion are equally valid:
- Proof as praticality.
- Proof as knowledge.
The chalenge beyond this point is: How to conciliate this two points?
Solving this can bring interesting new views on Mathematics and on Science in general.
great video and very well explained. it was a good refresher of 4 color theorem for me.
"... even though I kind of don't."
LOL!
Your videos are lovely! So joyous haha. Keep it up!
i thought this was in depth enough
often videos skate around subjects and expect the viewer to fill in the blanks, which isn't always a bad thing, because it's one way to get people to be creative
but going in depth reveals subtleties which are simple but only understood once you start digging and often it is those simple things which unlock a whole new perspective
like in another video where you described how some numbers are indescribable due to finite languages and sets of symbols, so simple, yet actually mindblowing that that simple of a problem makes those numbers unreachable
I loved the accuracy of your europe map.
And I love your videos.
9:13 - No. Here is an example:
1 - Green
2 - Yellow
3 - Purple
4 - Yellow
In this case Green-Yellow or Blue-Purple swap won't work.
But what works in general is ColorOf(1)-ColorOf(3) or ColorOf(2)-ColorOf(4) swap.
Muy buen vídeo, estuve alternando el vídeo con una demostración escrita y logré entenderla muy bien por lo menos el teorema de los 5 colores. Entender el de los 4 colores es un reto.
Yes on more in-depth videos! I love that the induction step in the proof can be done with color pencils. I'm not sure my discrete structures teacher would accept that to fulfill his annoying "in formal notation" requirement.
As always...Excellent video! Too long? No. Did you explain the theorem so I could understand it completely? 💯 yes! Thank you.
This was so interesting!! Also
What if we did a group collab between all six of us? I feel like that would be interesting.
I could quite literally listen to you all day!
The video was as long as logic required it to be. I don't mind longer videos, when they are informative, like yours. Keep up the good work.
Superb. Thanks a lot. Yes, in-depth videos are even better. Go on.
Hi Jade ! Great video! Now you could do a video with your friend about gaussian curvature (that is why you cannot draw an acurate map of the earth, even locally, as he says in his video). Another example of a mathematical invariant and a fundamental concept beyon general relativiy, as well !
I am a bit behind but I love all of your videos. Keep up and atom.
What an incredible channel.I seldom write comments,but I must say that this has to be one of the most important and interesting channels on TH-cam.
Do you think you could do a video on Euler characteristic and the classification of platonic solids as a wonderful application?
On the go in the depth point. As deep as you can go is perfect
Very well explained. Thank you.
I love this theorem a lot! Thank you :D
Superb vid. Thanks a bunch. Cheers
Great presentation, I learned a lot.
This is the best explanation of the four color theorem I have ever seen. Anyone who can solve equations on screen without it feeling intimidating can get my upvote.
Up and Atom, what happens if I have a map in which I have 6 nations with a main territory, but inside the main territory on each nation there are 5 enclaves (one for each of the other nations)? How many colors would I need if I want to color the enclaves of a given nation with the same color as the main territory?
Hi, This was a great one. Thank You for this much in depth video. This one was fairly descriptive of the topic. Loved this one also. It was worth the time you took after your previous video.
Thanks.
Finally it's worth waiting for though I am not big fan of maths but u make it easy to understand it😁
Great stuff. Thanks for posting.
Non-mathematician writing - what's been discovered about map colouring in higher dimensions?
In case of three-dimensional regions, where two regions must have a different color if they touch by a shape of positive area, arbitrarily many colors can be required. This is true even when the regions in question are cuboids (rectangular boxes).
Ken Appel (pronounced a-PELL) was a guest-lecturer for a day in my Math History class (for Math Education majors). It was really exciting to hear from the researcher himself.
I knew both of these men at the University of Illinois. The 'a' in 'Haken' is more like the 'a' in 'father'.
Great job!
My opinion is that this video did exactly what it was supposed to do. And to be very honest, my sense of time was not registering here... and that's a good thing. I take it as you kept your video interesting enough to keep my attention enough to lose track of time. In other words: it wasn't boring! ;) And as someone I consider a "science communicator," you fill that awkward position whose job it is to not only make science interesting, but to translate it into something most people can understand without "dumbing it down," or losing enough information that the explanation becomes useless.
And again, part of it I feel has to do with your charm and character. Let's put it this way, if Michael Cain had made this video, I probably wouldn't have watched it lol.
n_n
Love the new format
Reminds of grade school geometry, where you weren't given the actual size of the shapes, or real scale/design, but still needed to do proofs. I'd think the simplest answer for the 4 color theorem has to do with the limitations in siding across a plain. Even potentially expanding to the limitations in siding in 3d space. After the 3rd dimension, however--I doubt this theorem would still hold true.
I am impressed. VERY impressed. So well done!
Is the Euler Characteristic a function of 2D graphing, or does it still hold true for 3D graphs?
What about a hub and spoke? You have a region that's a central circle, then it's surrounded by regions that each abut it. We slice up those regions really thin so that there's a lot of them, like 12. We can't possibly fill them with 4 colors without having one of them use the same color as the central hub.
Not all the outer layers have to be different colors. I’m pretty sure what your describing can be done in 3
@@vibemaster4592 thanks, you just filled in the gap in my thinking! I can see the light...
I have only one question. since we don't color the outer face in the four colors theorem, doesn't the eular formula become:
V-E+F=1?
And then everything is proofed like the 5 color theorem.
Can someone explain please?
The short answer is that it doesn't matter if you include the outer face or not. You can always stick a frame around a given map to turn the old outer face into an inner face - so any example of a map which is only 4-colourable if you ignore the outer face gives a map which can't be 4-coloured even if you ignore the outer face.
Except we don't colour faces... We used that concept only to justify the Euler formula for planar graphs, but the actual target is to colour the VERTICES. :-B
As for the V-E+F=1... that is indeed the usual way the formula is stated for planar graphs, disregarding the "outer face", but V-E+F=2 is the more common form used for 3d solids (polyhedra). ;-)
Great explanation. And I adore how animated and bouncy you are.
1) How many colors would it take to do this in 3 dimensions?
2) How does the problem change as you add even higher dimensions?
Take a look at _Hadwiger's Conjecture,_ which could be regarded as a generalisation of _4CT_ in some sense. Bollobás, Catlin, & Erdős proved that it holds for _almost every_ graph in 1980, but the full conjecture itself remains inscrutable.
I confess I've not yet watched Jade's video (so I don't yet know how she regards the proof) but, having worked in the field, I would say that the thing that really distinguishes _4CT_ from other proofs is largely bound up with how little it offers, _per se,_ that might help us approach _Hadwiger._
Around 2:15;
Isn't the first "ladder proof" discounting some really important priors? Like gravity, height of the ladder, fitness, etc.
Excellent video, thank you!
Thanks for making this very usefull
Now THAT is a cool math video. Well done!
Congratulations! You did it more in depth than Numberphile, and not so packed that it would be not understandable. Very good video. I'll check others and perhaps Subscribe. And I'm giving a like to this video.
Thank you!
It's true for graphs on a plane and on a sphere... but for surfaces with higher genus it's not true! E.g. the 7-colouring of tessellations of the torus and their generalisations for higher-genus surfaces.
To me the answer to the question is simply, "How many countries share a point?" That then will be the number of colors that are required to avoid sharing a color boundary. That is unless you are of the mind that color sharing requires a line, which of course consists of two or more points.
If we are thinking that you cannot have two countries of the same color touching a point then another way to approach proving this problem would be to look at geometric shapes like square and hexagon's that perfectly nest together. And ask yourself what is the minimum number of colors required to not share a point, and for the squares it is 4, but for the hexagon it is 6. But theoretically all countries could be wedges of the same pie and reduce down to long skinny triangles that all share a central point. So colors touching the same point must be excluded from this equation.
hi jade! I often heard about "quantum radar"..what is it and how does it detects object. . it uses any quantum mechanics properties ?
jaikumar848 Quantum radar is a radar set that entangles its emissions at the transmitter such that it can detect whether or not a received radar signal is one that the transmitter emitted. Thus, it can differentiate its own signal against the noise floor, and detect remarkably small radar targets, such as stealth aircraft. So far, on paper, it sounds amazing. Unfortunately, the reality is harder. Entanglement requires very little interference or noise to begin with, and decoherence, or loss of entanglement caused by interaction with the environment, is one of the biggest problems. So while it is possible to construct, it's difficult to miniaturize and utilize in an austere environment. The wiki is pretty good on this. en.wikipedia.org/wiki/Quantum_radar?wprov=sfla1
jaikumar848 I’ve never heard of it! I’ll be sure to look it up :)
Up and Atom thanks Jade! why i am curious to know .. It uses quantum properties and second it can detect stealth plane like F-35
@@jaikumar848 any radar can detect an F-35, even a homemade one, stealth simply reduces the distance at which that radar can see it, by deflecting or absorbing enough of the signal so as to reduce the return signal below the noise floor at longer distances faster than a non-stealth aircraft. The unique ability of a quantum radar is that it can detect which received radar signals were transmitted by the quantum radar itself, so if you can ignore the radar noise floor, then you can detect a stealth aircraft even when the signal is less than the noise floor because it's no longer like trying to find a needle in a haystack, but rather like trying to find the same shiny needle against a flat matte background.
calvinstrikesagain thanks for info 👍
I love your videos either way!
i think of the 4 color therum differently
if there was 1 "shape" that is surrounded with N shapes, the center/one shape is s single color and if the amount of surrouning shape (N) is...
even- the color could be alternating only needing 3 colors 1 center 2 alternating
if N is ODD
then it can continue the alternating pattern until the last peice where a 4th color is needed
Well yes, proving that we need at least 4 colours is trivial. The tricky part is showing that no matter how large the planar graph gets, four colours are always enough.
Imagine the surrounding shapes being surrounded by more and more weird shapes (not arranged in neat concentric circles). Funny fact is that while 4 colours are always enough, figuring out if (for a given planar graph) 3 might also suffice is hard, even for computers!
If you could make a map with 5 countries all touching, you would need the fifth color. So long as caddy corner contact doesn't count as "touching", you can't, therefore you can always color them with 4 colors.
Not sure how to formally prove that you can't make such a map, though.
Does that mean that there can be no country with more than 4 neighboring countries, we can always add another neighbor by reducing boundaries which means then it cannot be colored by 5 colors. Infinite number of countries can be added which are directly connected to the main country. Please reply.
it's actually pretty easy to visualize this mentally once you're aware of it, the only way a map would need 5 colors is if it exists in more than 2 dimensions
You did Leave out one part of the ending: people have been trying to see if they can reduce the number of graphs to a human checkable number.
It's funny. I just started to draw blobs on a paper and realized that as soon as I had one blob touching three other blobs, it had to cover one of the first three with it, thus making it impossible for a fifth blob to touch all of the first four. No idea how to translate that to mathematics, though...
Great video, I really enjoyed it.
You probably should make a shorter version (more like a summary) for the general audience.
Color Theory is often used in compiler design when trying to match registers with variables.
I solved this years ago. Any area can be represented by a point placed arbritrarily within it. Points taken from four adjacent areas make a quadrillateral, the lines representing connecting common borders. Now add an extra point anywhere and line-of-sight limitation mean that there will always be a point which it cannot connect with, without crossing a line . Can't do the math, but these guidelines should lead to a solid proof.
Oh, the four colour theorem! Why isn't Willie's video in the info cards?
Don't worry! It's linked virtually everywhere else!
Kempe was right. The counterexamples of Errera, Heawood and others can successfully be resolved using Kempe chains. Since there are 6 possible combinations of Kempe chains, and they do not commute (applying BG and then BR is not the same as applying BR and then BG), there will always be a possible number of combinations of applying S6 to a node such that the color charge drops below 4, allowing it to be colored with the 4th color.
what is the font you used for writing in black