How to almost prove the 4-color theorem October 7, 2009

Posted by Noah Snyder in planar algebras, quantum topology.

Vaughan Jones often quips at the beginning of talks on Planar Algebras (see these lectures, for example) that the worst thing you can say about Planar Algebras is that they have not yet yielded a proof of the 4-color theorem. In this post I’ll sketch how a common “evaluation algorithm” (used by Greg Kuperberg and by Emily Peters, for example) almost proves the 4-color theorem. I believe this (failed) argument is due to Penrose, though I’m taking it from an article of Chmutov, Duzhin, and Kaishev and some notes of John Baez’s. There are some more elaborate attacks (by Kauffman, Saleur, Bar Natan, and probably others) that I won’t discuss at all. This is the second of what hopefully will be a short series of posts on “evaluation algorithms” (the first was on the Jellyfish algorithm).

The outline of the post is as follows. First I’ll explain a standard reduction of the 4-color theorem to a question about 3-coloring edges of trivalent graphs. Second I’ll explain why 3-colorings of edges is a question about finding a positive evaluation algorithm for a certain planar algebra. Third, I’ll discuss “Euler characteristic” evaluation algorithms. Fourth I’ll explain how this technique almost answers the 4-color theorem.

Suppose you have a planar graph and you want to 4-color the faces (note, I said faces, not vertices). First notice that you can reduce to the case of 3-valent planar graphs by “adding a new country at every higher valency vertex” (see Week 22 in Mathematical Physics for a delightful ASCII drawing). This observation is from the early days of the 4-color problem and due to Cayley and Kempe. The next reduction also comes from the 19th century, and is due to Tait. There is a bijection between “4-colorings of faces” and “4-coloring one distinguished face and then 3-coloring the edges.” The way to understand this bijection is to label the edges with “rules for changing face colorings.” Namely there are 3 ways to assign a pairing of the four colors. If you’ve chosen such a rule for every edge then you can propogate your single face coloring to the whole graph. It’s a simple exercise to check that this gives a bijection between valid colorings.

The invariant of planar graphs “number of 3-colorings of edges” extends to a planar algebra/TQFT/tensor category by the recipe similar to that Ben outlined here. Any planar graph with boundary can be thought of as a functional on the space Span{labelings of the boundary}. Extending by linearity any linear combination of planar graphs with boundary can also be thought of as such a functional. Mod out by the equivalence setting two diagrams equal to each other if they give the same functional. The key fact is that these relations play well with gluing together diagrams and hence gives a planar algebra (or tensor category together with a chosen generating object).

What explicitly do these relations look like? You can remove a bigon for a multiplicative cost of 2, a triangle for a multiplicative cost of 1, and a circle with no trivalent vertices for a multiplicative cost of 3. Furthermore there is a version of the I = H relation (I strongly encourage you to check yourself that this relation between number of 3-colorings of edges holds for any coloring of the boundary):

So what do we need to do to prove the 4-color theorem? We need to give a manifestly positive algorithm for evaluating closed diagrams in this planar algebra! That’s it.

One common technique for evaluating closed planar diagrams is to concentrate on the faces. Notice above we know that we can remove all bigons and triangles. What about bigger faces? Well the beautiful thing is that by Euler characteristic arguments all you need to do is prove that you can remove squares and pentagons because any planar diagram has a pentagonal or smaller face. In fact this technique and small variations on it have been remarkably successful at answer planar algebraic questions (once for quantum groups and once for an exotic subfactor).

So let’s try that. Here’s the square (finding this formula using the above relations is kinda fun):

Now there’s just one case left, the pentagon. Just find a positive formula there and you’d be done!

1. Greg Kuperberg - October 7, 2009

This is an important argument because it proves the “x-color theorem” for any real $x \geq 5$. This is of course using the chromatic polynomial to interpret a non-integer number of colors. It is still a conjecture that the chromatic polynomial is strictly positive for all real $x \geq 4$. Moreover, it’s an intriguing features of this question that it exactly corresponds to real values of the quantum parameter q.

2. Scott Morrison - October 7, 2009

This conjecture says “every planar network of 2-strand Jones-Wenzl idempotents evaluates to something positive” (at d=2 for the four colour theorem, but we might hope for all d>=2).

That suggests a generalisation in a different direction. It’s plausible that every planar network of arbitrary Jones-Wenzl idempotents is positive. You could think of this as saying “Every history of (quantum) angular momentum interactions which isn’t forbidden is allowed.” Here forbidden means that your trivalent graph labeled by naturals satisfies the usual triangle inequalities and parity restrictions (but in the language of JW idempotents this is automatic) and allowed means positive “amplitude” or evaluation.

3. Noah Snyder - October 7, 2009

Greg, where I can I find a succinct explanation of the general relationship between U_q(so_3) and the chromatic polynomial? (Namely that not only does q=1 correspond to the chromatic polynomial specialized at 4, but in general that the quantum group corresponds to the chromatic polynomial specialized at q+2+q^-1?)

4. Scott Morrison - October 7, 2009

I know you’ve found this already Noah, but for everyone else: http://arxiv.org/abs/0711.0016 is excellent.

5. Noah Snyder - October 7, 2009

Is 5 the smallest value of x (other than 4) such that the x-color theorem has been proved?

6. David Speyer - October 7, 2009

It can’t be quite that easy. Take the dodecahedron and quotient by the antipodal map. So you obtain a tiling of $\mathbb{RP}^2$ by six pentagons. The edge graph is the Petersen graph, which is not 3-colorable. If you could deal with the pentagon, wouldn’t this show that any surface tiled with pentagons had a 3-colorable edge graph?

In general, this is a heuristic for ruling out proofs of the 4 color theorem. Any proof must look at a sufficiently large neighborhood of the pentagon to see that we are not dealing with this tiling of $\mathbb{RP}^2$.

7. Noah Snyder - October 7, 2009

It’s not that easy, there’s a reason I called it a failed proof!

8. Greg Kuperberg - October 7, 2009

Noah: The succinct explanation is the Yamada polynomial. The Yamada polynomial is the link invariant of the adjoint representation of U_q(sl(2)). It is also an invariant of tangled trivalent graphs, because there is an invariant tensor in $V_2^{\otimes 3}$. If the graph is planar, then its Yamada polynomial is proportional to the chromatic polynomial of the face graph. One way to argue this is to check that the skein relations for n-gons are all the same when n ≤ 5.

Of course to get started you have to match x with q. The easiest way to do this is to check the 0-gon, i.e., a closed loop. A closed loop contributes a factor of x-1 to the chromatic polynomial, and it contributes a factor of [3] to the Yamada polynomial. So $x - 1 = [3]$, or $x = [2]^2 = q^2 + 2 + q^{-2}$.

I believe that x can be pushed down to $5-\epsilon$ in the skein proof of the x-color theorem. The way to understand the status quo is that the actual proof of the 4-color theorem is a lot like skein theory, except that it is skein theory with existential quantifiers rather than skein theory with enumerative equality. The extra idea (due to Heesch) is that the skein relations need some extra oomph which you can obtain by diffusing the local Euler characteristic. The diffusion of the local Euler characteristic (or the rule for diffusion) is called “discharging”. Probably some simple discharging rule implies the x-color theorem when x is close enough to 5.

I suspect that there hasn’t been a whole lot done with this conjecture.

9. Noah Snyder - October 7, 2009

Thanks. I’d sorted that out from the reference Scott mentioned above. The point where I was confused was that when I learned about the 4-color version of this I thought the reduction from 4-coloring faces to 3-coloring edges was an important intermediate step. But it seems the general connection between the Yamada polynomial and the chromatic polynomial doesn’t actually go through an intermediate step of edge coloring. Hence my confusion.

10. Greg Kuperberg - October 7, 2009

That’s right, it doesn’t. The Yamada polynomial model implies an alternate model of x-colorings in terms of a certain sort of edge 3-coloring with one oriented color and one unoriented color for the edges. This is just using the weight basis for the irrep V_2. What’s remarkable, and not fully explained, is the fact that the edges always have 3 states even though the faces have x states.

A closely related fact is that there is a functor from the fusion category of U_q(so(3)) to the fusion category of S_n, when n = [2]^2 = [3] + 1. The functor takes the adjoint representation to an n-1-dimensional irrep of S_n. Of course, S_n only has finitely many irreps while U_q(so(3)) has infinitely many, so irreps of the latter can’t all go to irreps of the former. Instead, most of them go to various reducible representations. Somehow there is an S_n sitting inside U_q(so(3)), or at least morally sitting inside.

As I think I mentioned when we met, there is an analogue of this for U_q(sp(4)). For one particular value of q, there is a functor to the fusion category of the Higman-Sims group. This was discovered by the late Francois Jaeger, and I have a paper on that. Or if you like, you can think of it as a relation between the U_q(sp(4)) polynomial of a certain type of planar graph, and the number of “Higman-Sims colorings” of its faces.

11. Noah Snyder - October 7, 2009

Another way of talking about the relationship between U_q(so_3) and S_t is that U_q(so_3) is the free version of S_t (free in the sense of free probability). Similarly, the free version of O_t is U_q(sl_2), and the free version of GL_t is “oriented Temperley-Lieb.” See work of Banica and collaborators.

Yup, you mentioned the connection between U_q(sp_4) and Higman-Sims when you were here in June. I’ve actually been thinking about some stuff related to this connection quite a bit over the summer, it’s not ready for the blog, but I’ve been meaning to email you about it at some point.

12. David Speyer - October 8, 2009

Noah: Fair enough. From your description, it wasn’t clear whether the problem is that the pentagon is not positive, or simply that no one can show it is positive. I think my argument shows that the problem is the former.

13. Noah Snyder - October 8, 2009

Yup, good point. It’s also not that hard to see that you can’t write the pentagon as a positive linear combination of forests directly. Notice that if there were a positive formula using the rotation action you could show that there was a positive formula which was also rotationally invariant. The space of rotationally invariant 5-leaf forests is just linear combinations of two things (1-tree and 2-tree forests). So you just need to show that those two vectors are linearly independent, and then find a non-positive formula. Showing linear independence could be done by computing some inner products. It seems plausible that somewhere in that inner product you end up with the graph that you mention, so perhaps this isn’t an independent argument.

14. Michael Welford - October 8, 2009

Finding the formula for the square does look like a fun challenge. Now I’ll have to leave this post up on my browser until I work it out. Of course, the whole ‘almost proof’ is just a slighty exotic variant of the original ‘almost proof’.

Going from 4 colors for faces to 3 colors for edges can be taken another step. I assign what I call a polaritiy to a vertex based the order of edge colors when going around the vertex clockwise starting with red. Red-white-blue has opposite polarity to red-blue-white. There is a face 4 coloring just when for each face the number of vertices on that face of each polarity are equal mod 3.

There. Now you have a fun challenge too.

15. dick lipton - October 10, 2009

Have you looked at our idea of approximate Tait colorings: at http://rjlipton.wordpress.com/2009/04/24/the-four-color-theorem/

16. Noah Snyder - October 11, 2009

I hadn’t seen that before. Thanks for sharing it. Awesome blog you’ve got going there!

17. Gil Kalai - October 12, 2009

Two questions: 1) Is Dror Bar-Nathan’s approach to the 4CT related? (It can be found here http://www.math.toronto.edu/~drorbn/LOP.html ).

2) Does the approach here gives a proof (to the easy theorems) that every bipartite cubic graph (or even every paipartite planar cubic graph) is 3-edge colorable? This is a nice toy problems for new approaches to the 4CT.

18. Noah Snyder - October 12, 2009

My understanding of Dror’s approach is that he gives a new description of planarity that is suggestive in the context of this argument. In particular, the planar algebra I gave above is nothing but integer spin representation theory of the lie algebra sl(2). What Dror does is give a lie theoretic description of planarity in terms of sl(n) for large n. So if you believe “everything about lie algebras really comes from sl(2)” then you should believe the 4-color theorem.

Since Dror’s approach uses actual lie algebras rather than quantum groups, at face value it only applies to 4-coloring not to x-coloring for x>=4. It would be interesting to see if his approach generalizes to the quantum group setting.

19. Carnival of Mathematics #59 « The Number Warrior - November 6, 2009

[...] The 4-color-theorem states that any map can be colored with at most four colors so no two adjacent regions share a color. It was proven in 1976 by Kenneth Appel and Wolfgang Haken using a computer to check 1,936 maps. Noah Snyder at the Secret Blogging Seminar almost but doesn’t quite prove the 4-color-theorem in a single blog post. [...]