48
$\begingroup$

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 An Update on the Four-Color Theorem by Robin Thomas. The paper 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.

Improve this question
$\endgroup$
10
  • 5
    $\begingroup$ 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. $\endgroup$
    – Michael Lugo
    Commented Mar 24, 2010 at 22:03
  • 3
    $\begingroup$ 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. $\endgroup$
    – Theo Johnson-Freyd
    Commented Mar 25, 2010 at 3:18
  • 9
    $\begingroup$ 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. $\endgroup$
    – Noah Snyder
    Commented Mar 25, 2010 at 5:53
  • 5
    $\begingroup$ 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. $\endgroup$
    – Bruce Westbury
    Commented Mar 25, 2010 at 6:11
  • 2
    $\begingroup$ @M.Winter Unfortunately, Robin passed away and his website is no longer available. I have added a new link to the paper. There were many valuable resources on Robin's website, so if anyone has a saved old copy, please let me know. $\endgroup$
    – Tony Huynh
    Commented Sep 20, 2021 at 9:18

5 Answers 5

Reset to default
16
$\begingroup$

There is a classical approach by Birkhoff and Lewis, which remained dormant for decades. It was recently revived by Cautis and Jackson (start here [“The matrix of chromatic joins and the Temperley-Lieb algebra”, J. Combin. Theory 89 (2003), 109–155] and proceed here [“On Tutte's chromatic invariant”, Trans. Amer. Math. Soc. 362 (2010), 491–507]), using the Temperley-Lieb algebra.

Improve this answer
$\endgroup$
0
19
$\begingroup$

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?"

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    Commented Mar 25, 2010 at 19:04
  • 2
    $\begingroup$ 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. $\endgroup$
    – Noah Snyder
    Commented Mar 25, 2010 at 23:39
13
$\begingroup$

Does "Lie Algebras and the Four Color Theorem" (Combinatorica 17, 43–52 (1997). https://doi.org/10.1007/BF01196130) by Dror Bar-Natan qualify ?

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Tony Huynh
    Commented Mar 25, 2010 at 5:17
  • 3
    $\begingroup$ 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? $\endgroup$
    – Tony Huynh
    Commented Mar 25, 2010 at 5:23
  • $\begingroup$ @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. $\endgroup$
    – David Lehavi
    Commented Mar 25, 2010 at 5:51
  • $\begingroup$ 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... $\endgroup$
    – Vladimir Dotsenko
    Commented Mar 25, 2010 at 8:59
8
$\begingroup$

There is an algebraic method by Alon and Tarsi which allows in certain cases to prove that certain graphs are $k$-colorable (in fact, even $k$-choosable). A famous case where this method prevails is to show that a graph on $3n$ vertices consist of edge-disjoint union of a Hamiltonian cycle and $n$ triangles is 3-colorable. This method can potentially show that graphs of cubic planar bridgeless graphs are 3-edge colorable which is equivalent to the 4CT. (So far it allows only to derive 3-edge choosability from the 4CT.)

(I suppose that various other speculative algebraic methods were proposed over the years. For example, I myself proposed to approach 4CT by finding algebraic/topological conditions for the existence of "Tverberg's partitions.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ It is surprising reduction, since planar graph is not always 4-choosable, hence applying polynomial method by Alon-Tarsi looks to be useless in 4CT. $\endgroup$
    – Fedor Petrov
    Commented Sep 13, 2015 at 8:05
  • 3
    $\begingroup$ Well, but for the dual formulation of edge coloring of cubic planar graphs we do have choosability! $\endgroup$
    – Gil Kalai
    Commented Sep 13, 2015 at 8:13
  • $\begingroup$ Yes, this is exactly what does astonish me in this story! $\endgroup$
    – Fedor Petrov
    Commented Sep 13, 2015 at 8:21
6
$\begingroup$

There are several reformulations by Matiyasevich, like this with polynomial, this with binomial coefficients modulo 7, also some others but they are less `algebraic', whatever it means.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .