"Geometric Combinatorics" refers to the interaction between discrete geometry and combinatorics. Convex polytopes, monomial ideals, oriented matroids, simplicial complexes, hyperplane arrangements are examples of geometric objects that encode combinatorial information. Applications across the mathematical sciences are numerous: for instance, the use of Newton polytopes and simplicial complexes in algebraic geometry and commutative algebra. At the same time the geometric objects above provide a wealth of enumerative and algebraic questions for combinatorialists. An example is the theory of f-vectors of polytopes.
Recently the study of f-vectors of convex polytopes has involved algebraic techniques represented by the cd-index. In the first paper the author discusses Infinitesimal Hopf algebras which give a general setting allowing one to lift the notions of Möobius function, ab-index, cd-index and eulerian, all commonly studied for polytopes or geometric complexes, to more general combinatorial objects. One of his results gives a simple and conceptual proof of the existence of the cd-index for eulerian posets.
The second paper provides an exact formula for the number of triangulations of the cyclic (n-4)-polytope with n vertices. The only other nontrivial closed formula counting triangulations of a polytope is that of the convex n-gon, the Catalan numbers. This paper is a step towards developing general tools for enumerating triangulations.
Multiplexes are self-dual polytopes whose specific combinatorial properties resemble certain properties of simplices. Ordinary polytopes generalize cyclic polytopes in the following sense: Their facets are multiplexes, where as the facets of cyclic polytopes are simplices; and they admit a vertex facet incidence matrix which satisfies Gale's evenness criterion. The third paper deals with completely describing the face lattice of multiplexes.
For a hyperplane arrangement A, Orlik and Terao constructed a certain commutative algebra U(A). In the fourth paper the author introduces a combinatorial analog of the algebra U(A). Namely, for an oriented matroid M, he constructs a commutative algebra A(M) that recovers the Orlik-Terao algebra U(A) when M is the oriented matroid of a hyperplane arrangement A. The results are then used to give a negative answer to a question by Terao and Orlik: is U(A) determined by the intersection lattice of A?
In the fifth paper the authors describe a family of polytopes whose lattice points exhibit a beautiful structure. The purely geometric description has a surprising algebraic consequences and gives a result on the minimum size of representations of sums of squares of polynomials, using the Newton polytope of the polynomial.
The main result of the sixth paper clarifies the relationship between two simplicial complexes naturally associated with a normal semigroup ring. The author gives a new and purely topological proof of the theorem of Danilov and Stanley describing the canonical module of a normal semigroup ring as the lattice points in the relative interior of the corresponding polyhedral cone.
The seventh paper introduces and studies the topology of three simplicial complexes: convex, acyclic, and free sets, all associated with an oriented matroid. These concepts were previously studied in diverse contexts. The main result of the paper states that for any simple oriented matroid the three complexes are in fact homotopy equivalent to each other and to either sphere or a point.
Oriented matroids also present interesting algorithmic problems. In the eighth paper, the authors propose algorithms for generating single-element extensions of a given oriented matroid. The algorithms make interesting use of the tope graph and the cocircuit graph.
The ninth paper is related to the well-known Evasiveness Conjecture for simplicial complexes and its generalizations. The main contribution of the paper is the construction of many examples of Z-acyclic vertex-homogenous simplicial complexes which are important `obstructions' to a general proof of the conjecture.
The last paper deals with triangulations of oriented matroids, a topic of interest not only in oriented matroid theory but also in connection to the "combinatorial differential manifolds" introduced by R. MacPherson in the 1990's. This paper presents a family of triangulations with very nice topological behavior.
We are grateful to Jacob E. Goodman and Richard Pollack for their enthusiastic support of this issue and to the referees for their hard work resulting in many helpful comments and corrections.
Guest Editors
Jesús De Loera,
Frank Sottile, and
Bernd Sturmfels.