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

Bivariate Splines and the Four Color Map Problem

This map of the United States was colored by Barrett Walls, in a project with Neil Robertson, Daniel P. Sanders, Paul Seymour and Robin Thomas. Reproduced with permission.

The Four Color Map Problem

The celebrated Four Color Map Theorem states that any map in the plane or on the sphere can be colored with only four colors such that no two neighboring countries are of the same color. The problem has a long history and inspired many people (including many non-mathematicians and in particular countless high school students) to attempt a solution. The question of whether four colors always suffice was first stated in 1852 by Francis Guthrie and remained unanswered until Appel and Haken came up with a book length proof in 1976.

Multivariate Splines

Multivariate Splines are smooth piecewise polynomial functions defined on a suitable tessellation of a two or three-dimensional domain. They have been my primary area of research since 1984.

The Problem

Probably the most famous open problem in multivariate splines is the question of a simple formula for the dimension of a particular spline space. Consider a triangulation, i.e., a tessellation of a polygonal domain by triangles (satisfying certain technical requirements). The splines of interest here are once differentiable everywhere on the domain, and they can be represented on each triangle as a polynomial (in two variables) of degree 3. The space of these splines is of great practical interest since it offers the possibility of interpolating to function values at the vertices of the triangles with the smallest possible polynomial degree.

The Connection

The spline problem appears to be extremely difficult. The reason for its still open status is not a lack of trying! The reason for the difficulty is the same as the reason for the difficulty of the four color map problem: it is hard to localize things! Whatever you do anywhere seems to affect matters everywhere else, in a manner that is difficult to disentangle.

This Page

This page and its attachments are organized around a talk first given at the Mathematics Department of Vanderbilt University on May 2, 1997. I'll describe the multivariate spline problem, the four color map problem, the connections, and a proof of a simple spline problem by four color map techniques. The hope is that ultimately the spline problem will yield to the four color map approach.