Atlanta, GA | Posted: January 1, 1994
Carsten Thomassen is a Professor of Mathematics at the Technical University of Denmark and a member of the Royal Danish Academy of Sciences and Letters. He got his Ph.D. in 1976 from the University of Waterloo. He is editor-in-chief of the Journal of Graph Theory and was awarded the Lester R. Ford Award by the Mathematical Association of America. He gave an invited lecture at the International Congress of Mathematicians in 1990. His research concerns discrete mathematics and more specifically graph theory.
In 1890, P. J. Heawood gave an upper bound for the number of colors needed to color a map on the orientable surface of genus g, i.e., the sphere with g handles added. About 80 years later, G. Ringel and J. W. T. Youngs showed that Heawood's bound (which tends to infinity as g tends to infinity) is best possible. For example, on the torus, seven colors are sufficient and, in some cases, also necessary for coloring a map.
In this lecture we describe a 5-color theorem for each surface: if every noncontractible curve intersects many countries of the map, then 5 colors are sufficient. There is no 4-color theorem of this type.
A square matrix is sign-nonsingular if each term in the standard expression of the determinant is nonnegative. The problem of recognizing such a matrix is important in studying sign-solvability of linear systems of equations.
The permanent of a square matrix is defined as the determinant except that the alternating factor is omitted. The permanent is difficult to compute. In 1913 Polya suggested that the permanents of certain matrices can be computed by transforming them into determinants of sign-nonsingular matrices by multiplying some entries by -1. We show how these (and other) problems are related to a fundamental problem in graph theory, namely that of finding a directed cycle of even length in a directed graph.