Using Ehrhart Theory to Solve Combinatorial Problems
Final Report Abstract
The focus of this research project was to take a look at combinatorial problems from the perspective of polyhedral geometry. At first glance, these two areas seem to have little to do with each other. Combinatorics, on the one hand, is concerned with finite problems, such as graph coloring, which is about assigning colors to nodes in a network such that nodes that are connected to each other directly get a different color. This problem arises, for example, when assigning frequencies to cells of a cell phone network, or when coloring the countries on a map. On the other hand, polyhedral geometry is about the study of geometric objects with flat faces called polytopes, such as cubes or tetrahedra. Ehrhart theory, in particular, is about studying patterns of lattice points inside such polytopes, e.g., by asking for a given polytope P how many points that have only integer coordinates are inside P ? It turns out that many combinatorial problems can be translated into the language of polyhedral geometry. For example, finding a coloring of a map with 100 countries can be rephrased as finding an integer point in a polytope in 100-dimensional space. This dramatic shift of perspective often leads to surprising new insights, as the geometric point of view allows us visualize and reason about the spatial relationship between different solutions of the original problem. For example, a link between two nodes in a network might correspond to a flat plane in 100-dimensional space and moving from one coloring to a different coloring would mean moving from an integer vector on one side of this plane to an integer point on the other. A key factor that makes such translations work are the languages of algebra and logic. Problems in combinatorics are readily formulated using logical expressions involving linear inequalities like x + y ≤ k, which provide the starting point for a geometric interpretation. In turn, functions counting the number of solutions in terms of a parameter like k often have special algebraic properties, such as quasipolynomiality. Such properties raise a number of natural questions that can guide the geometric investigations and often lead to surprising answers. The main publications of this project contribute to a deeper understanding of these connections. Most importantly the results of this project make the translation of combinatorial problems into a geometric setting more systematic and provide a number of generally useful new concepts and methods. First, the fact that many counting functions are quasipolynomials allows them to be evaluated algebraically at arguments for which they were not originally defined. Combinatorial interpretations of these resulting values are known as combinatorial reciprocity theorems. The geometric perspective has the remarkable power that it often leads naturally to such reciprocity theorems. In this project we have extended this approach considerably so that it applies not only to integer matrices of a very particular shape but to all integer matrices. Second, quasipolynomiality immediately raises questions about the coefficients of the quasipolynomials that appear. This project has lead to a novel interpretation of the meaning of these coefficients in terms of geometric objects and, by virtue of this insight, has produced a complete characterization of the quasipolynomials that can appear in a wide class of combinatorial problems. Third, this project has yielded a new and surprising connection between algebraic objects known as quasisymmetric functions and polyhedral geometry. One upshot is a method for constructing quasisymmetric functions for any combinatorial problem that can be expressed by any logical formula over inequalities x i ≤ x j , along with geometric tools for investigating their properties. Finally, a major success of this project has been the development of Polyhedral Omega, a new algorithm for solving linear Diophantine systems. For the first time, this algorithm connects both analytic and geometric methods for solving this type of problem. By virtue of this dual perspective, our new algorithm achieves cutting-edge performance while at the same time being far simpler than previous approaches. Moreover, geometric insight provides us with a deeper understanding of the computational complexity of this algorithm than analytic approaches previously allowed. Solvers of this type are useful in many contexts, ranging from theorem proving in pure mathematics to practical applications in optimization and statistics. The research in this project has highlighted how looking at combinatorial problems from a geometric perspective can not only help humans to visualize intricate mathematical phenomena but can moreover lead to important structural insights that are both illuminating and useful. This is particularly evident in the development of Polyhedral Omega, which was an unanticipated success of this project and which would not have been possible without this dual point of view. The results of this project have validated the polyhedral geometry approach to combinatorics and have raised a number of important questions for further investigation, which promise to be of both theoretical interest and practical merit and which I hope to pursue in future research.
Publications
- Ehrhart f ∗ –coefficients of polytopal complexes are non-negative integers, Electronic Journal of Combinatorics 19(4), P16, 2012
Felix Breuer
- Enumerating colorings, tensions and flows in cell complexes, Journal of Combinatorial Theory, Series A 122(4), 82-106, 2014
Matthias Beck, Felix Breuer, Logan Godkin, Jeremy L. Martin
(See online at https://doi.org/10.1016/j.jcta.2013.10.002) - Scheduling Problems, 39 pages, 2014
Felix Breuer, Caroline J. Klivans
- Polyhedral Omega: A New Algorithm for Solving Linear Diophantine Systems, 49 pages, 2015
Felix Breuer, Zafeirakis Zafeirakopoulos
