f-vectors of polytopes, spheres and arrangements

多胞体、球体和排列的 f 向量

• 批准号: 0757828
• 负责人: Edward Swartz
• 金额: --
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-06-15 至 2011-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0757828&HistoricalAwards=false
• 关键词: vectors; polytopes; spheres; arrangements

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.

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