f-vectors of polytopes, spheres and arrangements

本项目属于代数组合学领域，重点研究由几何、拓扑或代数-拓扑条件定义的各种有趣组合对象族的面向量特征。该项目的主要目的是一方面找到有用的组合运算，另一方面找到有用的代数构造，使它们之间的相互作用将在以下三个问题中产生一个解决方案，或至少是一个重大进展：简单球（也包括分段线性球和同调球）的f向量的表征；多面体环向g向量的表征在仿射半空间和半球的排列中找到（最多k）级复杂性的明显上界。基于定义上述族的拓扑、代数拓扑或几何条件，组合运算将被用于将问题简化为具有进一步性质的更简单对象的子族。对于给定的组合对象，将构建具有所需代数属性的代数结构-即推断我们所寻找的组合结果的属性。有时，PI计划颠倒组合学和代数的角色，并将合适的组合结构与给定的代数对象关联起来。已经取得了部分成果。该项目的主题是几个数学学科的交叉，包括交换代数、组合学、代数拓扑、几何和凸性。成功地解决所提出的问题也将使人们更好地理解这些学科之间的联系。来自f向量理论的代数工具将被应用于阐明计算机科学中重要的k集问题；因此，这个项目也将对离散几何和计算几何产生影响。它在计算机科学中的应用包括算法方面的应用，例如凸包计算，以及理论方面的应用，例如图的交叉数和凸多面体的广义下界定理。

This project lies in the area of algebraic combinatorics, focusing on the characterization of face-vectors of various interesting families of combinatorial objects defined by some geometric, topological or algebraic-topological conditions. The main aims of the project are to find useful combinatorial operations on one hand, and useful algebraic constructions on the other hand, such that the interplay between them will yield a solution, or at least a significant progress, in the following three problems: characterization of f-vectors of simplicial spheres (also piecewise linear and homology spheres); characterization of toric g-vectors of polytopes; finding sharp upper bounds on the complexity of (at most k)-level in arrangements of affine halfspaces and of hemispheres. Based on the topological, algebraic-topological or geometric conditions defining the above families, combinatorial operations will be used to reduce the problem to subfamilies of simpler objects with further properties. For given combinatorial objects, algebraic structures will be constructed, with desired algebraic properties - i.e., properties which infer the combinatorial consequences we look for. At times, the PI plans to reverse the roles of combinatorics and algebra and associate a suitable combinatorial structure to a given algebraic object. Partial results have already been obtained.The theme of the proposed project lies in the intersection of several mathematical disciplines, including commutative algebra, combinatorics, algebraic topology, geometry and convexity. Success in solving the proposed problems will yield also a better understanding of the connections between these disciplines. Algebraic tools from f-vector theory will be applied to shed light on the important k-set problem in computer science; thus this project will also have an impact on discrete and computational geometry. The applications to computer science include algorithmic ones, e.g. to convex hull computation, as well as theoretical ones, e.g. to crossing numbers of graphs and the generalized lower bound theorem for convex polytopes.