One well-known result in discrete mathematics is that the countries for any map can be given one of four colors so that any two countries sharing a border will have different colors. In mathematics, this result is usually stated as saying that any planar graph is four-colorable. The proofs of this result that are known involve checking hundreds of individual cases; the first proof of this result (given in 1976) was one of the first well-known mathematical proofs to involve computers in doing the checking. This project attempts a different route to obtain this proof, one that involves using the optimization of continuous functions to obtain a result that at first glance appears not to involve continuous quantities at all (since in the end one only wants to use one of four colors per country). The goal is to eliminate all the case-checking that went into the original proof. Such a proof would give further confidence to mathematicians that the original proofs did not miss any important cases. The project includes other problems that have this flavor of using continuous optimization to obtain results in optimizing discrete quantities. These include other results in trying to minimize the number of colors used in coloring general (non-planar) graphs, and finding practical algorithms to solve certain types of linear systems of equations. The research will be used as a means of outreach to undergraduates, and involve them in their project.
In particular, this project explores several new directions for progress on the interface of discrete and continuous optimization. The first returns to the technique of using semidefinite programming, an extension of linear programming, over the complex numbers to break through a nearly 20-year old barrier in coloring 3-colorable graphs. The second considers finding a direct proof of the famous theorem about four-coloring planar graphs via semidefinite programming. The third considers an eigenvector-based approximation algorithm for the maximum-cut problem due to Trevisan and looks for possible improvements and extensions. The fourth looks at an algorithm for solving Laplacian systems of equations due to Kelner, Orrechia, Sidford, and Zhu, and considers possible directions that might make the algorithm competitive with current linear-system solvers. These directions include batching updates and looking at a dual version of the algorithm. The fifth and final direction looks at an early result in spectral graph theory due to Hoffman and Singleton, and considers whether one remaining open issue in that paper can be resolved.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
