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.