A non-constructive proof of the Four Colour Theorem
arxiv.org
arxiv.org
These authors have long, established careers, with 2,000 MathSciNet citations between them. Waterloo is a hotbed of combinatorics; I doubt that they posted this before passing the paper around a bit.
Graph theory as a branch of mathematics is like photography as an art form: Anyone can point a camera, and one sees a lot of incredibly weak graph theory if one digs deep enough into the regional conference circuit.
This work is deep, relying on an understanding of generating functions that many casual practitioners don't possess. If the proof has a flaw, the issue will be technical and difficult to uncover. I love how people take the obvious bet that this is likely wrong because so many proof attempts have failed. In a prediction market, I'd bet on this proof being right.
There is a good amount of second-order evidence that the proof is wrong. Further, I skimmed the introduction, and it seems the indicated approach cannot possibly work. My guess is that both authors are senile. (They're quite old.)
If you give me decent odds, I'd be happy to bet against you regarding the proof's correctness. Would you take 1:1?
Are both of them senile?
Second-order evidence: Old mathematicians (~80). Famous problem. Weird, imprecise writing style. No mention of the proof by mainstream mathematical news sources (breakthroughs are usually accompanied by excited blogging/tweeting). No acknowledgements directed at other mathematicians who have checked or commented on the proof.
[deleted argument here; replaced by more precise comment below]
My tone is harsh because I think the best thing to do is to quietly ignore it, similar to how the community treated Atiyah's claims of a RH proof at the end of his life.
Have you seen this comment? https://news.ycombinator.com/item?id=34083099
> the argument looks like it's based on large n asymptotics, so even assuming everything works correctly the strongest statement they can hope to show is that the theorem is true for all n > n_0, where n_0 is some large constant. but there is no mention of this fact. the theorem is claimed for all n.
They're claiming:
> Theorem 7. If there is a map L which cannot be 4-coloured then only an exponentially small fraction of the maps with n edges can be 4-coloured.
These claims appear mutually exclusive.
>The argument looks like it's based on large n asymptotics, so even assuming everything works correctly the strongest statement they can hope to show is that the theorem is true for all n > n_0, where n_0 is some large constant. But there is no mention of this fact. The theorem is claimed for all n.
This is completely wrong. A proof for all n>n_0 is a proof for all n, since any counter-examples have to exist as subgraphs of arbitrarily large graphs.
Specifically I think section 4 is basically nonsense. (I see Sniffnoy has already pointed this out below.)
(Re: your comment, Theorem 7 is going to fail below the smallest counterexample, right? This is bad, imprecise writing - a red flag.)
If you think that's the best thing to do then why not do it?
To be clear, I don't like this state of affairs. As suggested above, the best course of action seems to be to ignore the posting.
It's so inappropriate that in the field that's actually trained for this, they're disallowed by compact, even with extensive evidence.
Please stop.
The field trained for this is not refraining from this because it's hard to get right, but because it undermines the privacy promise they give their clients! not an argument applicable to people who do not have that professional reputation to uphold.
Of course you should speculate about mental health of people when it's relevant to the topic - it's a factor heavily shaping many people's behaviour!
* No discussion of why they were not found by other people in the past.
* No discussion of how these techniques could be used on other problems.
* A lot of calculations which would be left out as trivial by most graph theory papers (for example, calculations about the edge counts of subgraphs)
I have no idea whether the proof is right or wrong, and I'm not so sentimental as to believe that the harsher person is more likely to be wrong. (Besides, naysayers are usually right, just like they are when predicting that any given startup will fail.) However, the HN guidelines (https://news.ycombinator.com/newsguidelines.html) ask you not to post like this and that's important too. Other users are making their case against the OP while following the guidelines just fine. Please be more like them.
There's no personal attack here. I'm sorry if that comment comes across as curt, but the post I responded is (in my opinion) grossly misleading and deserves pushback. For example, consider the statement: "If the proof has a flaw, the issue will be technical and difficult to uncover," made by someone claiming years of experience as a math professor thinking about this question. This is easily identifiable as wrong, because the purported proof is just 7 pages (actually less than that due to extraneous material) and does not use any particularly technical mathematics (a strong undergraduate major probably knows enough to comprehend what's going on). Indeed, people found the error in (less than) 12 hours after that comment was made.
The comment about senility is not a "swipe." It is a very real problem in the mathematics community. Mathematicians get old and are sometimes afflicted by dementia, and this unfortunately can manifest as hopeless attempts at famous problems. Atiyah's "proof" of the Riemann Hypothesis right before his death is perhaps the most well known example, but there are others that (thankfully) aren't disseminated publicly. In the pre-internet age, journal editors were able to make such things quietly disappear. But now we have the arxiv. This is valuable context for understanding why two mathematicians with distinguished publication histories might be posting an incorrect proof, which had not been provided by other comments.
That being said, I will endeavor to phrase such comments more carefully in the future. Thank you for your message.
Let's create a question on Metaculus!
The fact that this includes arguments which casual practitioners would not be able to confidently use in a crank proof does not evidence its correctness. It just shows us that it's from a different type of person, susceptible to making a different type of error.
OK, section 4.2 makes no sense to me. So they have this set Q, right? Which is the set of plane graphs that can be written G=A*B*C*D, where * denotes joining at a cut vertex. Their goal is to show that every G∈Q can be 4-colored, and then use that to argue that a nonzero fraction of plane graphs can be 4-colored, and then argue (via the generating functions and asymptotics) that this means that they all can be.
Except... if they can show that every G∈Q can be 4-colored, then all of this argument with generating functions and asymptotics is unnecessary, right? Because surely G can be 4-colored iff A, B, C, and D all can; and since A, B, C, and D can be any plane graph, that would be the end of it -- if you have a plane graph A and you want to 4-color it, all you'd have to do is stick a 3-path hanging off the end of it to put it in Q (indeed, in the subset they call \overline{Q}), and then 4-color that. The rest of the argument would appear to be unnecessary!
Meanwhile, their argument for why graphs in Q can be 4-colored doesn't seem to make any sense to me. It's inductive, but they haven't written it in a clear manner that makes it exactly apparent how they inductive hypothesis is used. I honestly do not see how they are justifying the statement "It follows from the Induction Hypothesis that S_1 is 4-colorable" -- it doesn't look like any work is being done, it all looks circular to me!
Am I missing something here?
(Apologies for no reference. I hope I'm not misremembering.)
There is a fun faith-shaking element to the story, though. The Four Color Theorem, as a proof, actually contains a couple thousand smaller proofs. These were generated and checked by a computer, but it is humanly possible to check them with a great deal of effort. There was a guy -- I forget his name, and Google isn't helping me! -- who, as his Ph. D. thesis, actually went through them and checked them. And IIRC, he found about a dozen errors! They weren't fatal -- he was able to repair them -- but that whole process didn't really reassure people. ;)
What I can tell you is that it wouldn't have been so straightforward as that. We're not talking about an axiom-to-result symbolic proof piece of software like you might attempt to write now. It wasn't a computer proof so much as a computer-assisted proof. Lots of human analysis to describe specific properties, and then a computer program to check that a long list of geometric configurations had those properties.
I don't know exactly what the program output as its proof, but I can only imagine the problems would have been small assumptions built into its design failing in corner cases. The theorem is notoriously difficult to reason about rigorously, and there have been a number of accepted proofs over the years that turned out to be false. It really doesn't help the whole situation that not only is it the first major computer-assisted theorem, it just happens to deal with a result that people are already wary of.
[0] https://projecteuclid.org/journals/illinois-journal-of-mathe...
I don't feel this is fundamentally different from the categorization of finite simple groups, which is also combining many small theorems and proofs, yet more widely accepted.
The proofs have the form:
1) Give the prover a challenge that they only have a 50% chance[B] of passing if they don't possess the private info.
2) Repeat as necessary with new, independent challenges.
3) If they keep passing, hooray! The probability that it's a faker decays exponentially. You can get really high confidence, very quickly!
Doing more rounds is just like re-running the computer proof.
[A] I first learned about the issue from reading the Scott Aaronson lectures that became Quantum Computing Since Democritus
[B] Doesn't have to be 50%, any figure will give the exponential decay and only require a linear increase in the number of rounds, so long as the probability stays the same between all rounds.
My comment above didn’t even mention randomization. That’s not necessary. All that’s necessary is that the tests be independent. Randomization is one way to achieve that but not a hard requirement.
Even so, it seems you do see the connection, you just dispute one element that you think is critical.
But they are obviously not independent.
This is like flipping a coin once, looking at the result 20 times in a row (without flipping it again), concluding you have magic luck powers since you got heads twenty times in a row, and that would be really unusual in the analgous system where you flipped a coin 20 times instead of just looking at it.
> Randomization is one way to achieve that but not a hard requirement.
This is besides the point, but pray tell. How do you reduce the probability of an algorithm being incorrectly programmed by means of running it multiple times without changing the input or introducing some randomness somewhere? I don't think that's possible. Really the ZKP case isn't even checking the algorithm but checking a specific user input is consistent.
I think this would be equivalent to denying that BPP without coin flips is P, which afaik it is.
> Even so, it seems you do see the connection, you just dispute one element that you think is critical.
I mean, i guess you could say that if you modify the system to add the connection you are trying to establish, then yes the connection becomes obvious.
Yes, independent with respect to the variable you're testing. In the ZKP, the independence is between the challenges given to the prover. In the computational proof, independence is between the probability of computational error affecting the calculation. (To be sure, you'd want to run the proof on different hardware!)
>> Randomization is one way to achieve that but not a hard requirement.
>This is besides the point, but pray tell.
Wait, what? Your original comment[1] was specific alleging that the absence of a randomizer completely broke the analogy:
>I fail to see the connection - new runs of the compuuter proof isn't going to randomize the code.
How would this be "beside the point" when it's the point you introduced? Did you forget the point you were trying to make?
>How do you reduce the probability of an algorithm being incorrectly programmed by means of running it multiple times without changing the input or introducing some randomness somewhere?
Even doing the same run on the same hardware would provide evidence against against the earlier result being a fluke (e.g. from cosmic rays), as I said before. But yes, as above, to round out the possibilities, you'd want different people to translate the proof into different languages and hardware and run it there -- that would likewise increase your confidence in the result, just like running different rounds of the interactive ZKP would.
>I mean, i guess you could say that if you modify the system to add the connection you are trying to establish, then yes the connection becomes obvious.
Sorry, are you really saying that you see no parallel whatsoever between:
a) Run the 4-color computer proof multiple times to increase your confidence that the result wasn't just luck, and
b) Run additional rounds of an interactive ZKP to increase your confidence that the prover wasn't just lucky?
If so, that feels like more of a you-problem.
If you were disputing that additional runs of the 4-color computer proof could increase your epistemic confidence in it, then you should have raised that in response to the original comment[2], not one (like mine) that accepted it and pointed out an analogous situation.
But i don't think that is the concern at hand. Yes, re-running can reduce probability of failures due to soft-memory errors and such. But does nothing against logic errors (or non-transient hardware errors). My understanding is the main concern with the proof is not that a cosmic ray hits RAM and flips a bit, but that either the logic may be wrong or a general epistimitic unease that no human directly inspected the cases of the proof.
In any case i said as much in my original comment. To quote: "excepting cosmic ray induced errors of course"
> Wait, what? Your original comment[1] was specific alleging that the absence of a randomizer completely broke the analogy:
Yes, i stand by that (although accept your point that independence not randomization is the salient property). I also maintain that whether or not it is theoretically possible to do independent tests without a randomness is irrelavent to the matter at hand. What matters is if rerunning the code was an independent experiment, not what could theoretically be possible. Even if there exists some non-random way to do that, its irrelavent to whether or not any method was used.
> Sorry, are you really saying that you see no parallel whatsoever between: > >a) Run the 4-color computer proof multiple times to increase your confidence that the result wasn't just luck, and > >b) Run additional rounds of an interactive ZKP to increase your confidence that the prover wasn't just lucky?
Yes.
Although for greater clarity, i would clarify (a) to say i don't see the connection to non-negligibly increasing your confidence the result of the 4 colour is correct. I agree (and said this in my very first comment) that it would increase your confidence that you didn't get an incorrect result due to a soft-memory error. I would say that relative to all the possible reasons why you might get an incorrect answer, transient hardware failure is very low, so the increase in confidence from rerunning is negligible because the meat of the question is programming error.
In the analagous situation, re-running the zkp gives an extremely high increase in confidence the answer is correct, usually at least halving the possibility of error.
> If you were disputing that additional runs of the 4-color computer proof could increase your epistemic confidence in it
Sure, although the original comment was a bit vauge as to exactly what they meant.
>Theorem 7. If there is a map L which cannot be 4-coloured then only an exponentially small fraction of the maps with n edges can be 4-coloured.
It's one of those things that seems obvious in retrospect — of course large random graphs should be likely to contain any particular graph! But it hadn't occurred to me in my own (very amateur) considerations of the problem.
Will be interesting to see if it's correct. We've gone from an argument too long for a human to read to one in just seven pages.
Theorem 7 in their paper is trying to count the number of graphs that contain a hypothetical 4-color counterexample if it exists. It's done by hitting a suitable generating function with a big analysis hammer to bound its coefficients, not by probabilistic means.
The rough sketch was to show that it was not possible to construct a map that required five colours: that if you take a blob of one colour, wrap it in three others, all four are touching the others, but you can't possibly add a fifth since it either only touches the outer three, or it has to prevent two of them touching to get to the inner one (then the non-touching ones could be recoloured the same).
To this day, although I of course realise I was having no groundbreaking thoughts and it did not constitute a proof, I do not understand why the actual proofs are so complex, or require so much computation? It eluded far greater minds for over a century - what am I missing that makes it so problematic?
Now you need to generalise that to maps with infinitely many regions.
You need to be really careful about things like "infinitely large map" ... if you want to talk about really large things then they are really large. But if you want to talk about infinite sized things then you need to be careful. There are traps in infinities, and this theorem is about finite maps (or equivalently, graphs).
Proving that a small, local sub-section doesn't require five colours is helpful, but no one has been able to extend that, because there is a kind of "spooky action at a distance" that can happen. Local decisions about colours can lead to implications across the other side of the structure. Proving that your local decisions can always be made in a way that doesn't cause problems elsewhere is the problem.
You are saying the sorts of things I've seen many times before, but you need to try to make complete, precise statements about exactly what you propose. So far all you've said is that you can't arrange five regions that all touch each other, and that's true. Now, exactly how do you extend that to a map with billions of regions?
> there is a kind of "spooky action at a distance" that can happen. Local decisions about colours can lead to implications across the other side of the structure. Proving that your local decisions can always be made in a way that doesn't cause problems elsewhere is the problem.
This is the bit I can't grasp - I honestly appreciate the responses and attempts to explain it, but it just (mistakenly, I can accept even if I don't understand) seems counter-intuitive to me. As in, intuitive that it extends, or that there's no such problem.
Maybe I just need to play with it on paper a bit, stumble into such a spooky action to get it.
> Now, exactly how do you extend that to a map with billions of regions?
I don't have the background for the precision you'd like I'm afraid (if I did, I'm sure I'd understand anyway!) but loosely - divide and conquer; a similar thing happens at the interface of all the 'sub-maps'?
> This is the bit I can't grasp
OK. Let me give you a collection of statements, each of which I can expand on, but which might give you a sense of the problem.
* Instead of colouring regions in a map we can colour vertices of a graph;
(put a vertex in each region and connect vertices if their regions share a border)
* If a graph can be three-coloured then it can be four-coloured;
(Any three colouring is a four colouring, but with no vertices of the fourth colour)
* An instance of colouring an arbitrary graph can be converted into an instance of colouring a planar graph;
(There is a "widget" that uncrosses edges)
* Given a number to factor, we can construct a graph such that three-colouring the graph will produce a factorisation[0];
(Graph three-colouring is NP-Complete, so this is even easier than that)
Broadly, we can construct a graph that has exactly one (up to permutation of colours) valid three-colouring. As you start to colour it you find that you have to make choices, on average about $4/3$ choices per vertex[1]. But the wrong choice results in not being able to complete the colouring, and you don't know which choice or choices were wrong.
So you get this "spooky action at a distance" thing going on.
Sometimes a planar graph can't be coloured with three colours, and sometimes it can but a colouring is hard to find. When we allow the extra colour it turns out that it's always possible, but it's not obvious that that should be the case.
That's an #ISS-level view of the ideas ... hope it helps.
[0] https://www.solipsys.co.uk/new/FactoringViaGraphThreeColouri...
[1] Beigel, R.; Eppstein, D. (2005), "3-coloring in time O(1.3289^n)"[2]
[2] https://en.wikipedia.org/wiki/Graph_coloring#cite_note-15
PS: I've upvoted you because I'm sure other people have the same questions, they're good questions, and they deserve answers.
From my napkin sketch to satisfy myself, I think you can show the same thing equivalently by saying 'and the edges are not allowed to cross' - but I don't know if that's something that exists in graph theory? (If so, it seems to me it should be used here? And if it is, well, finally we have a modicum of precision for what I'm trying to get at!)
Edit: OK, sorry, that is a 'planar graph'.
If you have a map in which you want to colour the regions, you can convert to a graph by putting a capital city in each region, then putting a road between two capitals of countries that share a border. Colouring the capital cities vertices) so that any joined by roads (edges) get different colours is exactly the same problem.
The graph-colouring problem is more general now, but every planar graph is equivalent to a map and vice-versa ... there is a one-to-one correspondence between these problems.
Now we move to the NP-Completeness of the 3-colouring of general graphs. That shows that this sort of thing is hard for the reasons I gave in the grandparent post.
"But" I hear you say "That's for general graphs, and not for planar graphs!"
Yes, but there is a way to convert a graph-colouring problem on a non-planar graph into an equivalent graph-colouring problem on a planar graph, so we neither gain nor lose much by consider just planar graphs.
So 3-colouring planar graphs is NP-Complete.
Then you get into my comments about making bad choices and having to backtrack, and spooky action at a distance.
Hope that helps.
And if we take the poset to be partial colorings ordered by inclusion, it's not the case that a maximal partial coloring must color the entire graph. Some partial colorings have made choices which prevent them from being extended any further.
[To be clear, whenever I say "coloring", I mean from a fixed set of colors. E.g., a 4-coloring.]
So somewhere in the argument, the finiteness of C must play a role. This is in ensuring compactness.
> there could never be an area of an infinitely large map that had five regions each needing a different colour
A more precise version (infinite -> finite, "...needing a different color looking only at that sub-map) is plausibly true. That doesn't help you though, because...
> maybe the 'outside' colours are the same - but in that case you could always just recolour them individually before putting them together
...this is false. Five patches of one sub-map might touch one patch of the other sub-map. So now you'd have to prove that the first sub-map can be colored with three colors to rescue your proof of the FCT. Further...
> you take two such sub-maps, put them next to each other [...]
...your argument here seems to boil down to "I can construct the full map by gluing together sub-maps". Depending on how you constrain the sub-maps to prove necessary properties (see above), this may not be true. But even if it were, your argument that it works seems to only consider gluing together two sub-maps of specifically size five, which obviously does not allow you to construct maps with more than ten patches.
This makes for two to three fully deal-breaking errors in your proof sketch.
But colours-at-distance can be forced, so proximity isn't needed to create the need for another colour.
The theorem is difficult for two meta-reasons. One is that there are arbitrarily many planar configurations, and you need to prove that they are all four-colourable. The other is that whether or not a planar graph is three colourable is NP-Complete, and showing a planar graph is five-colourable is fairly easy, so it's on the boundary between fairly easy and really hard.
The proof that every planar graph (equivalently every map on a plane) is five colourable proceeds by showing that there is a small set of sub-graphs such that every graph must contain one (an unavoidable set), and then showing for each of those that it cannot be in a minimal counter example. This is easily done by hand.
Appel and Haken's proof of the four-colour theorem proceeded the same way, but the unavoidable set was large. The computation was to confirm that the set was unavoidable, and that each element was reducable. This involved a huge amount of tedious bookkeeping, best done by machine, but it was really just "doing the sums". The real work was creating a finite amount of bookkeeping that would then constitute a proof.
>The proof that every planar graph (equivalently every map on a plane) is five colourable proceeds by showing that there is a small set of sub-graphs such that every graph must contain one (an unavoidable set), and then showing for each of those that it cannot be in a minimal counter example. This is easily done by hand.
Isn't this missing a crucial point? You seem to be saying:
1. There is some (small) set S of graphs, all of which are 5-colorable
2. Every planar graph has at least 1 sub-graph in S
3. Therefore, all planar graphs are 5-colorable
But, from statements 1 and 2, one can only conclude that every planar graph _has a sub-graph_ that is 5-colorable, not that the entire graph is 5-colorable.
Don't you also need to prove that the complement of the sub-graphs is 5-colorable?
> The proof that every planar graph (equivalently every map on a plane) is five colourable proceeds by showing that there is a small set of sub-graphs such that every graph must contain one (an unavoidable set), and then showing for each of those that it cannot be in a minimal counter example.
You said:
> Isn't this missing a crucial point? You seem to be saying:
> 1. There is some (small) set S of graphs, all of which are 5-colorable
This is not what it's saying. It's saying that these graphs cannot be in a minimal counter-example. That's different from simply saying that they are 5-colourable.
> 2. Every planar graph has at least 1 sub-graph in S
> 3. Therefore, all planar graphs are 5-colorable
No, you've missed a bit of my comment. I said:
> showing for each of those that it cannot be in a minimal counter example.
So we have an unavoidable set U. So for every graph G there is an element S of U that is a sub-graph of G.
But we have also shown for every element S of G that any graph containing S cannot be a minimal counter-example. We're not showing that these elements S of U are themselves 5-colourable, we are showing that any G containing S is not a counter-example to the theorem.
So now suppose the theorem is false. That means there is a graph that requires 6 colours. From among those choose a minimal one, so M is a minimal counter-example. But the set U is unavoidable, so there is a S in U that is a subgraph of M. But any graph containing S cannot be a minimal counter-example, and we have our contradiction.
Hence there are no counter-examples, and the theorem is true.
For the Five Colour Theorem the unavoidable set U has only four graphs, so it's easy to check by hand. For the Four Colour Theorem in the original proof there were around 2000 elements of U, so it was infeasible to check by hand. That has been reduced to 633 graphs in U, but it's still tough to check by hand.
The paper in the original submission here takes a different approach.
> showing for each of those that it cannot be in a minimal counter example
I read "those" as "those subgraphs" rather than "those graphs".
Thanks.
That is the correct reading; your mistake must be elsewhere?
>> [the proof] proceeds by showing that there is a small set of sub-graphs such that every graph must contain one (an unavoidable set), and then showing for each of those that it cannot be in a minimal counter example.
No minimal counterexample to the claim [that a planar graph is 5-colorable] can contain any of these subgraphs. All planar graphs contain at least one of these subgraphs. Therefore, all planar graphs fail to satisfy the predicate "this graph is a minimal counterexample to the claim that all planar graphs are 5-colorable".
The elaboration is very explicit that the theorem is "for every subgraph S in the unavoidable set U, that subgraph (S) cannot be contained in any minimal counterexample":
>> we have also shown for every element S of G that any graph containing S cannot be a minimal counter-example.
The proof that every planar graph (equivalently every map on a plane) is five colourable proceeds as follows.
Cleverly produce a set U of small graphs S that have the following properties:
1: For every graph G, there is an S in U such that S is a sub-graph of G;
2: If G is a counter-example to the theorem, and S from U is a sub-graph of G, then there is a smaller graph H that is also a counter-example.
This is enough, because now let M be a minimal counter-example. By (1) there is an S from U that is a sub-graph of M. But by (2) there is then a smaller counter-example, contradicting the minimality of M. So there can be no counter examples.
With that now in mind, here is the original statement:
We proceed by showing that there is a small set of sub-graphs such that every graph must contain one (an unavoidable set), and then showing for each of those that it cannot be in a minimal counter example. This is easily done by hand.
I hope that helps.
Loosely because
a) it only shows it for such maps that contain such a blob. Who says other maps with five countries are easier to four-color?
b) it doesn’t rigorously show it. That you (and me, and everybody who looked at it) can’t find a way to draw that fifth area that touches all others doesn’t say much. what are your arguments for showing you looked hard enough?
For a similar case, read about the Jordan curve theorem. In layman’s terms, it says closed curves on a plane have an inside and an outside part (https://en.wikipedia.org/wiki/Jordan_curve_theorem). Naive readers think it’s so trivial to not require a proof, and it took mathematicians a while to figure out that it needed one. I don’t know the details, but mathematicians may have observed that that theorem also is true on a sphere but isn’t true on a torus (a closed loop ‘around the hole’ in the torus doesn’t have an interior and an exterior). So, they needed an explanation as to why it’s true on a plane or a sphere but not on a torus (the answer essentially boils down to “because a torus has a hole in it”, but that requires a rigorous definition of what a hole is)
"An actual map may have billions of countries and need not even contain “a blob of one colour, wrapped in three others”."
In fact every map of interest will contain a blob wrapped in at least three others.
But they are right that the problem is showing that the theorem holds for maps with billions of regions, or more. Decisions you make early in the process of colouring the map can turn out to be wrong, but only much later as you are trying to colour the last few.
In short, you are saying "I can't see how it can go wrong", but that's not enough ... there are things that might happen that you weren't able to imagine, and that's part of why proofs like this are hard.
Also, the theorem is true, and that makes it hard to explain why it might go wrong. Because we now know that it doesn't.
The grand-parent comment also says:
"... the Jordan curve theorem ... is true on a sphere ..."
The stronger form is not true on a sphere. The stronger form says that every topological sphere in 3-space has an interior that's retractable to a point and an exterior that's retractable to a shell. But the Alexander Horned Sphere[0] is a counter example.
In short, weird things you didn't suspect can happen, so proofs are sometimes harder than you think, even for "obvious" things.
https://old.reddit.com/r/math/comments/zruc58/221209835_a_no...
I have always wondered about this sample. Consider the possible 4-colours to be red, blue, green and orange, as in the image. We need to determine the colour of the black square. All 4 colours are joined in this inverted cross like formation and the center of the cross (a gray pixel atm) kind of indicates an infinity point. If the space in which these colours are drawn is not discrete, then they can all be said to join at the center of the cross.
Is this sample just not allowed by the rules of the "game"?
Consider it an extreme case of gerry-mandering...
Consider the gray pixel in the center a placeholder, much like Escher's place holder in the above image (because he couldn't think of how to realistically depict what turns out to be the infinite fractal nature of the center)
> An edge, no matter how small breaks the cross.
My very weak intuition says that an edge of infinite smallness would not.
Now make N as large as you like.
So allowing this makes the problem uninteresting, and precluding it makes the problem interesting and hard.
(I don't recall details - but the preconditions of the Four Colour Theorem rule out all the fuzzy sets, infinitely crooked lines, "this region is all points with one rational and one irrational coordinate", and other trickery that folks who've had a bit of math might otherwise be tempted by.)
In the original problem statement, you could solve by re-assigning your green region to be orange, your red region to be blue, your black region to green, and the white regions to red. Also note that regions that meet at a single point (as in your example) are not considered to be adjacent.
There is no limit to how many regions can surround and be in contact with a given region, it's just that the shared border that defines "in contact with" must be of non-zero length.
Note also: we are dealing with finite maps. That means that for any given map there will be a shortest boundary for that map, but it doesn't mean there is a minimum constraint.
> The approach uses a singularity analysis of generating functions for particular sets of maps, and Tutte's enumerative and asymptotic work on planar maps and their chromatic polynomials
Err yeah, so easy...
(This is intended seriously, but I do love the ironic twist compared to historical hesitancy to accept the computer assisted proof.)
If it's not correct, then HN is the place to find where's the error.
By elimination of disjunction, upvote ;)
Can this also prove the more general Hadwiger's conjecture?
Edit: Quoting a comment by bakkoting:
> Terence Tao is also concerned about that section: https://mathstodon.xyz/@tao/109554420101377184 .
That's not a good sign.