### Computing in Tropical Geometry

Zuse Institut Berlin (ZIB), Germany, on May 11-12, 2017## List of abstracts

In this talk, I will explain how the study of the tropical analogue of linear programming bring new results in relation with two notoriously open problems in computational optimization. The first problem, known as 9th Smale's problem, is the existence of a strongly polynomial time algorithm for linear programming. The second one is whether or not mean payoff games (a class of repeated zero-sum games with perfect information) can be solved in polynomial time. These contributions are obtained by tropicalizing standard algorithms in linear programming, namely the simplex and interior-point methods. This is joint work with Pascal Benchimol (EDF R&D), Stéphane Gaubert (INRIA and Ecole Polytechnique) and Michael Joswig (TU Berlin).
Mirror symmetry relates Gromov-Witten invariants of an elliptic curve with certain integrals over Feynman graphs. We prove a tropical generalization of mirror symmetry for elliptic curves, that is, a statement relating certain labeled higher genus Gromov-Witten invariants of a tropical elliptic curve to more refined Feynman integrals. This implies the tropical analogue of the mirror symmetry statement, and, by proving a correspondence theorem, the mirror symmetry statement itself. The results are complemented by a Singular package for computing Hurwitz numbers of the elliptic curve as Feynman integrals. The talk will address theoretical and a variety of computational aspects of the topic. This is joint work with Arne Buchholz, Kathrin Bringmann, and Hannah Markwig.
In economic theory, mechanisms serve as game theoretic models of abstract institutions e.g. auctions, voting procedures and contracts. We will discuss how tropical convex geometry and tropical combinatorics can be used to study such problems. We will discuss recent advances and problems motivated by economics. This is joint work with Ngoc Tran.
Laman graphs model planar frameworks that are rigid for a general choice of distances between the vertices. There are finitely many ways, up to isometries, to realize a Laman graph in the plane. Such realizations can be seen as solutions of systems of quadratic equations prescribing the distances between pairs of points. Using ideas from algebraic and tropical geometry, we provide a (deterministic) recursion formula for the number of complex solutions of such systems; a (probabilistic) algorithm for the same number in terms of the cardinality of a zero-dimensional tropical variety will also be presented. This is a joint work with Jose Capco, Georg Grasegger, Christoph Koutschan, Niels Lubbes and Josef Schicho
Mustafin varieties are flat degenerations of projective spaces induced by a choice of an n-tuple of lattices in a vector space over a non-archimedean field. These varieties have a rich combinatorial structure as can be seen in pioneering work of Cartwright, Häbich, Sturmfels and Werner. In this talk, we give a new description for Mustafin varieties in terms of images of rational maps, which were studied by Li. We completely classify the irreducible components of Mustafin varieties associated to a tuple of lattices. We relate Mustafin varieties for convex point configurations to Shimura varieties and certain moduli functors which appear in the limit linear series theory developed by Osserman called prelinked Grassmannians. Our methods include tropical convex hulls and tropical intersection theory. This is joint work with Binglin Li.
In this talk we will discuss the problem of computing the Berkovich minimal skeleton for curves. A technique using abelian covers will be presented. This technique uses Galois theory to obtain a highly symmetric graph that projects down to the desired minimal skeleton. Using this technique, we can find the minimal skeleton for genus 3 curves for instance, where the associated Galois group will quite often be the symmetric group on three elements. In fact, the technique can be used to compute the minimal skeleton for all curves up to genus 7. In the talk we will mainly focus on genus 3 curves and compute a lot of examples.
Deciding if a polynomial ideal contains monomials is a problem which can be solved by usual Groebner basis techniques. Deciding if a polynomial ideal contains binomials is more complicated. We show how the general case can be reduced to the case of zero-dimensional ideals using projections and stable intersections in tropical geometry. In the case of rational coefficients the zero-dimensional problem can then be solved via Ge's algorithm using methods by Babai, Beals, Cai, Ivanyos and Luks. In case binomials exist, one can be computed. This is joint work with Thomas Kahle and Lukas Katthän.
Curves of genus two can be described as a hyperelliptic cover of the projective line by a plane curve. Igusa invariants are rational functions in the branch points of the cover which can be viewed as coordinates on the moduli space of curves of genus two. We study tropicalizations of curves of genus two both abstractly and in plane coordinates of the hyperelliptic cover, and relate tropicalizations of Igusa invariants to lengths data of tropical curves. The approach involves computations of tropicalizations of curves using modifications, and refinement computations for moduli and Groebner fans. This is joint work with Maria Angelica Cueto.
This is a software demonstration on computations related to tropical linear spaces in polymake. There are many different ways to represent and construct tropical linear spaces, for example as tropicalization of ordinary matrices and linear ideals or, combinatorially, as matroid subdivisions. We will also demonstrate current developments in this area.
Semidefinite programming is a fundamental tool in convex and polynomial optimization. It consists in minimizing the linear functions over the spectrahedra (sets defined by linear matrix inequalities). One of the basic algorithmic questions associated with semidefinite programming is to decide whether a spectrahedron is empty or not. It is unknown whether this problem belongs to NP in the Turing machine model, and the state-of-the-art algorithms that solve this task exactly are based on cylindrical decomposition or the critical points method. We study the nonarchimedean analogue of this problem, replacing the field of real numbers by the field of Puiseux series. We introduce the notion of tropical spectrahedra and show that, under genericity conditions, these objects can be described explicitly by systems of polynomial inequalities in the tropical semiring. We demonstrate that these inequalities arise from Shapley operators associated with stochastic mean payoff games. As a consequence, we show that tropically generic semidefinite feasibility problems over Puiseux series can be solved efficiently using combinatorial algorithms designed for stochastic games. This is joint work with Xavier Allamigeon (INRIA, Ecole polytechnique) and Stéphane Gaubert (INRIA, Ecole polytechnique).
Given a real polynomial \(f \in \mathbb R[x] = \mathbb R[x_1, \ldots, x_n]\), we study the real tropical geometry associated with the question of how \(f\) behaves for \(\|x\| \to \infty\). This question is tied to the real Lojasiewicz exponent of \(f\) at infinity, and \(f\) is called coercive if \(f(x) \to +\infty\) whenever \(\|x\| \to \infty\). In 2015, Bajbar and Stein have provided a sufficient combinatorial criterion of coercivity for the situation that \(f\) has a very sparse support set. In the talk, we present a tropical approach to this criterion, which also allows to characterize the order of growth at infinity for that class. (Joint work with Cordian Riener.)
In the early days of tropical geometry, Speyer and Sturmfels posed the following problem: Give an algorithm for finding all irreducible factors of a given polynomial f. This problem and most of its variants are NP-hard, even for polynomials in two variables. In this talk, we give an algorithm for factorization and rational factorization that works on a large 'nice' class of polynomials. Joint work with Bo Lin.
This talk will be an introduction to cellular sheaves and their recent implementation in polymake. Our main focus will be the tropical cohomology of Itenberg, Katzarkov, Mikhalkin and Zharkov. Under suitable assumptions on a tropical variety this cohomology theory can recover Hodge numbers of complex projective varieties. One condition is that the tropical variety must be compact. Thus, we will present recent work on computing tropical compactifications of tropical varieties. Last Updated: May 11, 2017 |