Using Ehrhart Theory to Solve Combinatorial Problems

点击翻译按钮获取中文摘要

The topic of the proposed research project is the application of geometric methods, Ehrhart theory in particular, to problems in enumerative combinatorics. Ehrhart theory is the theory of counting integer points in polytopes. Here, a polytope is the set of solutions of a system of linear inequalities and its Ehrhart polynomial counts integer points in dilates. Applications range from the counting of solutions to optimization problems in operations research to the evaluation of box splines in numerical analysis.This project focuses on applications of Ehrhart theory to counting functions which are defined in purely combinatorial terms. Ehrhart theory associates geometric objects with these counting functions, thus offering a new and often helpful perspective on the combinatorial problem at hand. The proposed project explores three new directions for research:1) The application of results from Ehrhart theory requires a process of geometrization in which the combinatorial description of a counting function is translated into the language of polytopes. The research objective is to systematize this process and to transform methods for geometrization into algorithms. The goal is to extend methods from Ehrhart theory to work directly with counting functions defined in a combinatorial language, e.g., in terms of logical formulas.2) An important open problem is to find combinatorial interpretations for the coefficients of Ehrhart polynomials. The objective is to attack this problem from a new angle, by considering Ehrhart polynomials of a new class of geometric objects: unimodular cubical complexes.3) In order to extend the scope of Ehrhart theory to include functions which are not quasi-polynomials, the objective is to study multivariate Ehrhart functions. This leads to the investigation of Dedekind cotangent sums and their computational properties, which may yield an alternative to Barvinoks algorithm for counting lattice points in polytopes.