| Michael Joswig |
| Lars Kastner |
Modelling objects from algebraic geometry in the language of polyhedral combinatorics has been a success story as it paves the way to algorithmic and experimental methods. The purpose of this project is to investigate how derived and more complicated objects can be combinatorialised, too.
Historically, the starting point for combinatorial methods in modern algebraic geometry were toric varieties [1]. The geometry of a projective toric variety is controlled by a single lattice polytope or, more precisely, by the polyhedral fan spanned by its faces. This approach is based on a fixed embedding of the toric variety. More recently, tropical geometry came into the picture [4]. This connects algebraic geometry with combinatorics and optimisation. A large part of tropical geometry is also based on fixed embeddings, and it is still a major challenge to develop a suitable abstract setting beyond tropical curves. Nonetheless, abstract algebraic varieties, without any fixed embedding, are very desirable. Relevant examples include moduli spaces and varieties which arise as quotients, for instance, by some finite group action. Dealing with abstract algebraic varieties in terms of systems of affine charts is an obvious choice — yet the combinatorial and algorithmic ramifications are extremely intricate. One reason which makes computations difficult is the sheer size of the relevant objects.
Our main goal is to develop a new concept of abstract polyhedral fans with a view toward algebraic geometry. We will focus on data structures, algorithms and interesting examples. This will require to study several specific sub-problems in geometric combinatorics, computational complexity and algebraic geometry.
Consider all regular triangulations of a given point configuration. Every regular triangulation can be induced by attaching weights to every point, then taking the convex hull of the lifted points and projecting all the faces down that are visible from below. This procedure is often referred to as taking the lower hull of the lifted polyhedron. For a fixed regular triangulation the set of all weight vectors inducing this triangulation forms an open cone and the closure of this cone is called the secondary cone of this triangulation. All secondary cones together form a fan, the secondary fan.
Secondary fans are the first main structures we want to examine. If the point configuration has a symmetry action, then the secondary fan inherits this action. One main obstacle is to produce the secondary fan for a given point configuration. The main software for this task is TOPCOM, but for larger examples it will consume too much memory and be too slow in general. These problems can be overcome using a different algorithm, namely budgeted down-flip reverse search (see [2]). This algorithm is output-sensitive and parallelized. It is implemented in mptopcom which is based on TOPCOM, polymake and mts.
First runs of mptopcom have produced very promising results. For example we were able to produce all regular triangulations of the three-dimensional simplex dilated by a factor of three. Other examples include products of simplices and cyclic polytopes. The triangulations of the latter ones are connected to higher Stasheff-Tamari orders.
The cyclic polytope C(n,d) is the convex hull of n distinct points on the d-th moment curve. The triangulations of C(n,d) using only the vertices carry two different poset structures: One is given via downflips, the other arises from the canonical embedding of C(n,d) into C(n,d+1). These two orders are the two higher Stasheff-Tamari orders and it is an open question whether they coincide (see [3]).
Using mptopcom, we can produce the triangulations of C(n,d) for much higher n and d than before. This allows us to search for counterexamples to the equality of the two higher Stasheff-Tamari orders or to give stronger evidence for the equality of the two orders. mptopcom not only produces the triangulations, but also the full graph for the first Stasheff-Tamari poset given via flips.