Using Ehrhart Theory to Solve Combinatorial Problems

拟议的研究项目的主题是几何方法的应用，特别是Ehrhart理论，在枚举组合学的问题。Ehrhart理论是计算多面体中整数点的理论。在这里，多面体是线性不等式系统的解的集合，其Ehrhart多项式在膨胀中计数整数点。应用范围从计算的解决方案，以优化问题的运筹学在数值analysis.This项目的评价箱样条侧重于应用Ehrhart理论，以计数功能，这是定义在纯粹的组合术语。Ehrhart理论将几何对象与这些计数函数联系起来，从而为手头的组合问题提供了一个新的、经常是有用的视角。该项目探索了三个新的研究方向：1）应用Ehrhart理论的结果需要一个几何化的过程，其中计数函数的组合描述被翻译成多面体的语言。研究的目标是将这一过程系统化，并将几何化方法转化为算法。我们的目标是扩展Ehrhart理论的方法，直接与组合语言中定义的计数函数一起工作，例如，2）一个重要的公开问题是找到Ehrhart多项式系数的组合解释。我们的目标是从一个新的角度来攻击这个问题，通过考虑一类新的几何对象的Ehrhart多项式：么模立方复形。3）为了扩大Ehrhart理论的范围，以包括功能，这不是拟多项式，我们的目标是研究多元Ehrhart函数。这导致调查的Dedekind余切和和他们的计算性能，这可能会产生一个替代Barvinoks算法计算格点的多面体。

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.