Peter Alfeld, --- Department of Mathematics, --- College of Science --- University of Utah

Multivariate Splines and the 4 Color Map Problem





Notes

I'll start with a description of the four color map theorem, including a brief history and a quick summary of its proof. Then I'll describe the bivariate spline space of interest and open problems, including some very difficult ones. In the proof of the four color map theorem the assumption is made (without loss of generality) that no more than three countries meet at any one point. The argument then proceeds in terms of the dual graph of the map which associates one point with each country and connects each point to every point that corresponds to a neighboring country. Very intriguingly for a spline person, the result is a triangulation!

The space of real interest is S13, the set of all once differentiable functions that on each triangle can be written as a polynomial of degree 3. However, things get easier as the polynomial degree increases, and much of the talk is taken up by explaining everything in in terms of S14. There is a simple dimension statement that can be proved easily using standard spline techniques. I'll describe that proof, and then give an alternative proof that's based on the Four Color Map ideas.

The essence of the four color map proof is to assume that the statement is false, and that there are some maps that require five colors. If so there must be a smallest one. Any such smallest map contains at least one of an unavoidable set of reducible configurations, and can therefore be reduced to a smaller map requiring five colors. That of course does not make sense, we have a contradiction, and the assumption that there is a map requiring five colors is false. So four colors suffice!

Unavoidability means the same for splines as it does for the four color map problem. Reducibility, however, is very different. I'll discuss both concepts.

A major ingredient of the four color map proof that carries over directly to splines is the construction of unavoidable sets via a technique called discharging. I'll describe that technique and give some examples.

It appears that an inevitable consequence of the four color map approach as applied to splines is the need to state and prove statements applying not just to the triangulation but also to subsets of it. That gives rise to some interesting complications that seem to be manageable, however.

The fond hope in this project is that ultimately questions concerning multivariate splines can be settled using four color map techniques.

[21-Apr-1997]