Ancestors

Toot

Written by Vince Vatter on 2024-09-19 at 18:03

I wrote about Jackson and Richmond's supposed "proof" of the Four Color Theorem for Cantor's Paradise on Medium, giving a bit of the social media history of the "proof" and pointing out the fatal flaw.

https://www.cantorsparadise.com/on-the-supposed-nonconstructive-proof-of-the-four-color-theorem-5049e3eee366

=> More informations about this toot | More toots from VinceVatter@mathstodon.xyz

Descendants

Written by Zack Weinberg on 2024-09-19 at 23:56

@VinceVatter I don't quite follow the argument why Richmond–Robinson–Wormald Theorem A implies 4CT; it seems like there could still be a family of exceptions to 4CT as long as they are meagre relative to the set of all triangulations. Or to put it another way, it seems like the strongest statement Theorem A could possibly imply is that almost all triangulations (in the same technical sense) can be 4-colored.

=> More informations about this toot | More toots from zwol@hackers.town

Written by Vince Vatter on 2024-09-20 at 03:43

@zwol It doesn't; that's the point of my article... to show that it does imply 4CT would be to essentially prove 4CT by other means anyway. But Theorem A is a true statement, and a rather standard one at that.

=> More informations about this toot | More toots from VinceVatter@mathstodon.xyz

Written by Zack Weinberg on 2024-09-20 at 14:46

@VinceVatter Sorry, I oversimplified. What I'm actually stuck on is Corollary B. I do not see how "all triangulations can be 4-colored" follows from "a positive proportion of all triangulations can be 4-colored" plus Theorem A. It seems to me that these two premises combined do not rule out the existence of a nonempty, infinite, but zero-proportion set of exceptions.

=> More informations about this toot | More toots from zwol@hackers.town

Written by Zack Weinberg on 2024-09-20 at 17:28

@VinceVatter ... Unless maybe you can rule out the existence of such a set by observing that the set of all triangulations is countable (I think it ought to be but I'm not sure) and therefore its zero-proportion subsets must be finite (again I think this is true but am not sure of it) but if there's even one counterexample to 4CT then there must be an infinite number of them (definitely true; you can always add another region to the map).

But even if that entire chain of reasoning is 100% true, relying on it feels like cheating to me. (This may make more sense if I admit to being not fully on board with the axiom of choice.)

=> More informations about this toot | More toots from zwol@hackers.town

Written by Vince Vatter on 2024-09-20 at 17:41

@zwol Assume there was a counterexample triangulation T that cannot be 4-colored. Then all the triangulations that contain T cannot be 4-colored either. By Theorem A, almost all triangulations contain T. So, if a positive proportion of all triangulations can be 4-colored, that means it cannot be the case that there is even a single triangulation that cannot be 4-colored.

=> More informations about this toot | More toots from VinceVatter@mathstodon.xyz

Written by Zack Weinberg on 2024-09-20 at 18:11

@VinceVatter I regret to say that reads as just repeating the statement of Corollary B and does not clarify anything for me.

The sticking point for me is the passage from "a positive proportion of all triangulations can be 4-colored" to "there cannot be even a single triangulation that cannot be 4-colored". Given Theorem A I believe "if we could prove the proportion of 4-colorable triangulations to be > 0, then the proportion must be 1." But I don't yet believe that is the same thing as "not even a single exception can exist."

I think this is because I am not convinced that the set of all triangulations containing the hypothetical minimal counterexample T cannot simultaneously be "almost all triangulations" and "almost no triangulations", if that makes sense? Sure, in natural language that would be ridiculous, but I know how slippery infinite sets get.

=> More informations about this toot | More toots from zwol@hackers.town

Written by Vince Vatter on 2024-09-20 at 18:15

@zwol The following statements cannot both be true.

1. Almost all triangulations cannot be 4-colored.

2. A positive proportion of triangulations can be 4-colored.

If a single triangulation cannot be 4-colored, Theorem A implies that 1 is true. So 2 cannot also be true.

=> More informations about this toot | More toots from VinceVatter@mathstodon.xyz

Written by Zack Weinberg on 2024-09-20 at 18:46

@VinceVatter This is the exact thing I am not convinced of. Where can I find a proof that those two statements cannot simultaneously be true?

=> More informations about this toot | More toots from zwol@hackers.town

Written by Vince Vatter on 2024-09-20 at 19:57

@zwol Maybe the confusion is coming from the definition of "almost all". Almost all means a proportion of 1.

On the other hand, positive proportion means a proportion of > 0.

1+x > 1 if x > 0, and you can't have a proportion greater than 1.

=> More informations about this toot | More toots from VinceVatter@mathstodon.xyz