11 ms·
A non-constructive proof of the Four Colour Theorem
- zeroonetwothree 4y agoI haven’t read this carefully yet but I’m initially skeptical that it’s that easy.
- naasking 4y agoFrom the abstract: > 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...
- burnished 4y agoThat quote is so dense with words that individually are old friends, but paired up that way are as strangers to me.
- mkaic 4y agoThat was a surprisingly prosaic way to communicate this feeling, are you by chance a writer? If not, you should write more!
- ectopod 4y agoOf writing, prosaic means unpoetic, i.e. dull.
- mkaic 4y agoOh, my mistake! I've always (incorrectly) thought it meant "being prose-ful" or "reminiscent of poetic prose". My intention was to compliment @burnished's writing :P
- thombat 4y agoHe might just be Buster Scruggs' less melodious & more bookish brother.
- selimthegrim 4y agoFlajolet and Sedgewick have a nice book on Analytic Combinatorics that covers this
- ykonstant 4y agoI highly recommend that book; it can be dense, but it is a treasure trove of information.
- qsort 4y agoIf it's correct, then it's a wonderful approach. If it's not correct, then HN is the place to find where's the error. By elimination of disjunction, upvote ;)
- EGreg 4y agoHardly I doubt HN is that place Can this also prove the more general Hadwiger's conjecture?
- feet 4y agoWith the amount of incorrect comments I see on HN, definitely not. I'm not saying that I'm not included in that group, but I think we all are
- onos 4y agoAgree on the first part. If correct, it is a wonderful achievement, apparently built upon the work of at least two others.
- gus_massa 4y agoHN is good to spot crackpots, linbait and other kinds of papers that are very bad. This was posted by ColinWright, so my guess is that it's not obviously bad. If it has an error, it will need like a month or a year to be discovered. Anyway, I hope to see in a month a new discussion when Tao (or someone) have enough time to understand it. Edit: Quoting a comment by bakkoting: > Terence Tao is also concerned about that section: https://mathstodon.xyz/@tao/109554420101377184 https://mathstodon.xyz/@tao/109554420101377184 . That's not a good sign.
- lairv 4y agoSo until now every proofs of this theorem were still computer-assisted right ?
- notafraudster 4y agoWaterloo has a Department of Combinatorics and Optimization? Amazing.
- mwnorman2 4y agoNot only does Waterloo have a world-class C-&-O department, they also had a hero from Bletchley Park - Dr William Tutte, a kind gentle genius that never bragged about his accomplishments (he didn't talk about it, even to his family!) He broke the 'Lorenz' cipher (generally regarded as much more difficult than Enigma) Almost all modern Graph-theory and Matroid analysis is built on his work. --- Mike Norman, B.Math UofW 1986
- bodhiandphysics 4y agoTutte's are the central results in this work
- scythe 4y agoMost of this proof is very dense. But Theorem 7 seems like an interesting tactic that allows the authors to infer nonexistence from rarity: >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.
- bodhiandphysics 4y agoThis is in fact a very common proof strategy in combinatorics, often known as the probabalistic method. Naturally it was invented by Paul Erdos
- sweezyjeezy 4y agoI think that's a bit different - in the probabilistic method you show that if you randomly sample a graph (say) then the probability of it having some property is > 0 - therefore there must exist some graph having the property. 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.
- krsrhe 4y ago
- Strilanc 4y agoGiven the history of false proofs of the four color theorem surviving scrutiny for decades, I think I'll wait for this to be verified by a computer proof language such as Lean before trusting it. (This is intended seriously, but I do love the ironic twist compared to historical hesitancy to accept the computer assisted proof.)
- civilized 4y agoA short paper like this will almost certainly be either verified or refuted by the traditional method of mathematicians reading and analyzing the proof's logic. Computer-aided proof is pretty niche in mathematics.
- deleted 4y ago[deleted]
- NelsonMinar 4y agoMy memory is that the Four Colour Theorem was one of the first computer search-assisted proofs which caused all sorts of epistemological questions. Specifically how to know whether the software had no bugs and ran correctly, and how re-running to get the same result only lowered the probability and did not yield absolute certainty. Seems sort of a quaint concern now. (Apologies for no reference. I hope I'm not misremembering.)
- Dove 4y agoYou're remembering entirely correctly! I gave a talk on the Four Color Theorem as part of my master's degree in 2001, and it was a somewhat active epistemic debate among mathematicians at the time. I took the position that examining code was no different than examining a proof, that running it through a computer was no different than running it through your brain, and that mathematicians are not shy at all about "automating" processes over uncountable infinities in proofs, so why should we be shy about automating them over thousands mechanically? 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. ;)
- Dove 4y agoAMS has a good summary: https://blogs.ams.org/mathgradblog/2014/06/29/color-theorem https://blogs.ams.org/mathgradblog/2014/06/29/color-theorem
- ghusbands 4y agoTo save others the effort of reading - this only discusses the proof and not the by-hand check or "about a dozen errors" mentioned in the parent post.
- 4y ago
- OJFord 4y agoI'm not a mathematician, but when I was in school I read a lot of 'pop math', and fancied myself a lot better at it than I was (or am). I was fascinated by things like the FCT, and recall writing a document ...I don't think I kidded myself proving it, but at least 'understanding' it. 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?
- bodhiandphysics 4y agoin some sense because there might be strongly non-local effects... an assignment of color in one part of the graph can have an effect on what colors are allowed in a very different part of the graph. Planarity assures some degree of "locality", you can't arbitrarily connect one point to another point.
- nicky0 4y agoYour proof sketch actually suggested that it was not possible to construct a map with five regions that require five colours. Now you need to generalise that to maps with infinitely many regions.
- OJFord 4y agoBut as a result there could never be an area of an infinitely large map that had five regions each needing a different colour. I understand people are saying but you take two such sub-maps, put them next to each other, and maybe the 'outside' colours are the same - but in that case you could always just recolour them individually before putting them together?
- 4y ago
- Phemist 4y agohttps://imgur.com/a/WJKb9fT https://imgur.com/a/WJKb9fT 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...
- Phemist 4y agoThis is btw equivalent to a graph with 5 nodes, where all nodes are connected to every other node, which would quite obviously be impossible to colour with just 4 colours.
- klyrs 4y agoIt's not, though. If the four corners are sharp, blue & red are not adjacent, nor are green & orange. You can re-paint blue to red and orange to green, and you're left with a proper 3-coloring. Alternately, if the grey pixel takes another color (say, red) so that blue, green and orange are all adjacent to it, then green & orange are not adjacent -- re-paint orange to green, and you get a 4-coloring. Finally, if the grey pixel is its own region, you're effectively back in the first case and you can paint it black to obtain a 3-coloring.
- drbacon 4y agoThe "countries" are supposed to share an edge. An edge, no matter how small, breaks the cross.
- Phemist 4y agohttps://blog.artsper.com/wp-content/uploads/2022/08/escher-2.jpeg https://blog.artsper.com/wp-content/uploads/2022/08/escher-2... 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.
- Syzygies 4y agoI'm a math professor who has lost years to this question. I've met various authors involved in successful proofs. My 1976 grad school application from the University of Illinois came postmarked "Four Colors Suffice" (Appel, Haken). I've also been inundated with well-intended crank proofs of every tar pit like this. One can tell the difference without focusing one's eyes. 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.
- ngvrnd 4y agowell put.
- ruuda 4y ago> In a prediction market, I'd bet on this proof being right. Let's create a question on Metaculus!
- bakkoting 4y agoHow about Manifold? https://manifold.markets/ZviMowshowitz/will-the-new-nonconstructed-proof-o https://manifold.markets/ZviMowshowitz/will-the-new-nonconst...
- ColinWright 4y agoI caught a rumour of this paper about 6 months ago, so I'm pretty sure that in the meantime it's been evaluated and assessed by colleagues. So I'm pretty sure it's going to be right, with only small fixable things that need tidying up.
- 4y ago
- Sniffnoy 4y agoReposting my comment from /r/math: 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?
- spekcular 4y agoYou're not missing anything.
- sebzim4500 4y agoFrom my reading, it looks like can't make up their mind about whether Q = {X . Y: X, Y graphs} or Q = {X . Y : X, Y in Q}. Neither definitions seems to work everywhere.
- paulpauper 4y agoI am sure this is wrong. You cannot use asymptotic analysis on this problem. The assumptions it makes in section 4 does not necessarily prove or is specific to the 4-color theorem. Just splitting vertices etc. does not suffice to prove it for 4 colors, it can also prove it for 5 etc.
- mjreacher 4y agoSome comments on the math subreddit by some folks going through the proof in case anyone with a more formal background is interested: https://old.reddit.com/r/math/comments/zruc58/221209835_a_nonconstructive_proof_of_the_four/ https://old.reddit.com/r/math/comments/zruc58/221209835_a_no...
- raphlinus 4y agoAs a followup, this proof has now been declared as fatally flawed by John Carlos Baez, with some additional analysis by Noam Zeilberger. The argument is beyond my personal mathematical knowledge, but I would consider this a pretty definitive verdict. [1]: https://mathstodon.xyz/@noamzoam/109567981846531700 https://mathstodon.xyz/@noamzoam/109567981846531700