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]