Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

4-Colour Theorem. Every planar graph is 4-colourable.

This theorem of course has a well-known history. It was first proven by Appel and Haken in 1976, but their proof was met with skepticism because it heavily relied on the use of computers. The situation was partially remedied 20 years later, when Robertson, Sanders, Seymour, and Thomas published a new proof of the theorem. This new proof still relied on computer analysis, but to such a lower extent that their proof was actually verifiable. Finally, in 2005, Gonthier and Werner used the Coq proof assistant to formalize a proof, so I suppose only the most die hard skeptics remain.

My question stems from reading this paper by Robin Thomas. In it, he describes several interesting reformulations of the 4-colour theorem. Here is one:

Note that the cross-product on vectors in $\mathbb{R}^3$ is not an associative operation. We therefore define a bracketing of a cross-product $v_1 \times \dots v_n$ to be a set of brackets which makes the product well-defined.

Theorem. Let $i, j, k$ be the standard unit vectors in $\mathbb{R}^3$. For any two different bracketings of the product $v_1 \times \dots \times v_n$, there is an assignment of $i,j,k$ to $v_1, \dots, v_n$ such that the two products are equal and non-zero.

The surprising fact is that this innocent looking theorem implies the 4-colour theorem.

Question. Is anyone working on an algebraic proof of the 4-colour theorem (say by trying to prove the above theorem)? If so, what techniques are involved? What partial progress has been made? Or do most people consider the effort/reward ratio of such an endeavor to be too high?

I think it would be interesting to have an algebraic proof, even a very long one, particularly if the algebraic proof does not use computers. Given its connection to many other areas (Temperley-Lieb Algebras), the problem seems to be amenable to other forms of attack.

share|improve this question
1  
On the other hand, if it turns out that a proof of the four-color theorem via this fact also reduced to checking some very large number of cases, that might be evidence that there is some amount of irreducible complexity in the proof of 4CT. –  Michael Lugo Mar 24 '10 at 22:03
1  
Noah Snyder has some ideas about what must be checked --- I can't remember if they're here on MO or over at Secret Blogging Seminar. See also R. Penrose, "Applications of Negative Dimensional Tensors", Combinatorial mathematics and its applications, 1971. –  Theo Johnson-Freyd Mar 25 '10 at 3:18
    
I attempted a purely algebraic proof of the result for a research paper in a MATHEMATICA course a few years ago,Tony-nothing came of it. I still think it's an avenue worth chasing down. –  Andrew L Mar 25 '10 at 5:50
3  
It's not accurate to say that any of those ideas are mine. As to the original question, it's certainly something that lots of quantum topolgists think about on and off (Kauffman's written multiple papers on it, Bar Natan wrote a paper mentioned below, Vaughan Jones says "the worst thing you can say about planar algebras is that they haven't yielded a proof of the 4-color theorem yet" etc.). If anyone actually solves it we'll all hear about it. It's certainly something in the back of everyone's mind. –  Noah Snyder Mar 25 '10 at 5:53
2  
My view is that at the moment this is an isolated problem and that to make progress in needs to be understood in the right context as one of a class of similar problems. –  Bruce Westbury Mar 25 '10 at 6:11

3 Answers 3

up vote 9 down vote accepted

There is a classical approach by Birkhoff and Lewis, which remained dormant for decades. It was recently revived by Cautis and Jackson (start here and proceed here), using the Temperley-Lieb algebra.

share|improve this answer

Does "Lie Algebras and the Four Color Theorem" by Dror Bar-Natan qualify ?

share|improve this answer
    
At first glance I would say no, although I will have to read the paper more carefully. It seems to me that the bulk of the paper is spent proving that the 4-colour theorem is equivalent to a 'reasonable' statement about Lie algebras. This equivalence is certainly important, but to me the relevant question is why aren't people trying to prove this 'reasonable' statement about Lie algebras. What is the point of translating a theorem into the language of another field if one doesn't plan to use the methods of that other field to prove the original theorem? –  Tony Huynh Mar 25 '10 at 5:17
1  
To be provacative: would the Taniyama-Shimura conjecture have been proven if Fermat's Last Theorem had already been proven with the aid of computers? –  Tony Huynh Mar 25 '10 at 5:23
    
@Tony: I'm not sure myself if it qualifies (that's why I asked). However, if you want an algebraic proof, you have to start by translating it into some algebraic setting. –  David Lehavi Mar 25 '10 at 5:51
    
I believe this paper by Bar-Natan is mentioned in the paper of R.Thomas linked in the original post, with a comment that there is an equivalence there, not an independent proof... –  Vladimir Dotsenko Mar 25 '10 at 8:59

I must admit I'm a bit baffled about what the question is here, and about why so many people have voted it up. What are you looking for in an answer? I don't think it's appropriate to post speculation on the internet about which mathematicians are privately working on which big problems. As to public work, you seem to have a weirdly restrictive view of what "working on" and "partial progress" mean that don't fit with my understanding of how mathematics works. Several papers have been written on the subject of possible algebraic proofs of the 4-color theorem (look at google scholar or Mathscinet for papers which cite the Saleur-Kauffman paper mentioned in the paper you're reading), but if the Bar-Natan paper doesn't count for you then you're likely to be disappointed by all of them.

The long and short of it is that everyone in quantum topology would love to prove the 4-color theorem and occasionally thinks about it. There's lots of tantalizing clues that an algebraic argument has promise, but if anyone knew how to prove it they'd have done so. As far as I know there isn't anyone who is holed up in their attic thinking about only the 4-color theorem, instead there's a lot of people who every time they find a new tool think "hrm, I wonder if this tool would work on the 4-color theorem?"

share|improve this answer
    
Hi Noah. I think a reasonable answer was given by Igor, and I'll probably accept his answer once I've looked at the Cautis and Jackson paper more carefully. In another sense, I think the question is also a general probe into the current state of affairs in areas related to the 4-colour theorem. So, your second paragraph was quite helpful. Indeed, if you could elaborate or provide a link on what you feel remains to be checked that would be very helpful. –  Tony Huynh Mar 25 '10 at 19:04
    
Thanks for not taking my criticism personally. I think "what remains to be checked" is not quite the right way of thinking about it. What you have is a tensor category given by generators and relations, and you want to understand why all closed diagrams evaluate to something positive. There are lots of other tensor categories given by generators and relations, and people find new techniques for dealing with them all the time. The hope is that someday the right new technique will crack the 4-color theorem. –  Noah Snyder Mar 25 '10 at 23:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.