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.
  1. Outline of Talk
  2. The 4 Color Map Problem
  3. Proof of the 4 Color Map Theorem
  4. Bivariate Spline Spaces
  5. Generic Dimensions
  6. Conjectures
  7. Triangulations
  8. Combinatorics of Triangulations
  9. A simple proof for S14
  10. Subtriangulations, dim S14 on Subtriangulations
  11. Unavoidable Sets
  12. Discharging
  13. An Unavoidable Set for S14
  14. Reducible Configurations
  15. Reducible Subtriangulations
  16. Examples
  17. Example 1 - a 5-star
  18. Example 2 - a 5-substar
  19. Example 3 - a 4-star
  20. Example 4 - a 4-substar
  21. Reducible Configurations for S13
  22. Another Unavoidable Set
  23. Covering Sets
  24. Part of an unavoidable Set
  25. Remarks
  26. More Remarks
  • All the slides on one page

  • [01-Nov-2023]

    Go to Peter Alfeld's Home Page.

    Designed for netscape.