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.
-
Outline of Talk
-
The 4 Color Map Problem
-
Proof of the 4 Color Map Theorem
-
Bivariate Spline Spaces
-
Generic Dimensions
-
Conjectures
-
Triangulations
-
Combinatorics of Triangulations
-
A simple proof for S14
-
Subtriangulations, dim S14 on
Subtriangulations
-
Unavoidable Sets
-
Discharging
-
An Unavoidable Set for S14
-
Reducible Configurations
-
Reducible Subtriangulations
-
Examples
-
Example 1 - a 5-star
-
Example 2 - a 5-substar
-
Example 3 - a 4-star
-
Example 4 - a 4-substar
-
Reducible Configurations for S13
-
Another Unavoidable Set
-
Covering Sets
-
Part of an unavoidable Set
-
Remarks
-
More Remarks
All the slides on one page
[01-Nov-2023]
Go to Peter Alfeld's Home Page.