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.
