News for hackers. Stuff that matters.
Re:A Non-Constructive Proof of the Four Colour Theorem by Sniffnoy on Wednesday December 21, 2022 @04:49PM (#34086844)
Reposting 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?

Re:A Non-Constructive Proof of the Four Colour Theorem by spekcular on Wednesday December 21, 2022 @05:27PM (#34087240)
You're not missing anything.
Re:A Non-Constructive Proof of the Four Colour Theorem by sebzim4500 on Wednesday December 21, 2022 @05:55PM (#34087480)
From 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.
Re:A Non-Constructive Proof of the Four Colour Theorem by srcreigh on Wednesday December 21, 2022 @06:50PM (#34087946)
Where does Q = { (S1 . T1) . (S2 . T2) : S1,S2,T1,T2 in Q } not work?
Re:A Non-Constructive Proof of the Four Colour Theorem by isaacg on Wednesday December 21, 2022 @10:35PM (#34089466)
This definition fails because Q-bar needs to be a subset of Q, but in Q-bar, the graphs T1, S2, and T2 are specified to be the single-edge graphs e1, e2, e3. But single-edge graphs are not in Q.
Re:A Non-Constructive Proof of the Four Colour Theorem by bakkoting on Wednesday December 21, 2022 @07:29PM (#34088218)
Terence Tao is also concerned about that section: https://mathstodon.xyz/@tao/109554420101377184
Re:A Non-Constructive Proof of the Four Colour Theorem by kazinator on Wednesday December 21, 2022 @09:39PM (#34089034)
An inductive hypothesis mentioning some independent variable like n needs to look like a conditional, e.g.: "If all maps in Q with at most n-1 edges are 4-colorable, then all maps with at most Q(n) is 4-colored, all maps in Q with at most n edges can be 4-colored" and then it has to be shown.