Workshop on Combinatorics, polytopes, and complexity

February 19-23, 2018


Week schedule



9:30-10:30 Raman Sanyal

Title: A combinatorial theory of valuations on polytopes

Abstract: The confluence of Minkowski addition and volume gives rise to the vast theory of mixed volumes and intrinsic volumes. Mixed volumes and the related geometric inequalities have applications in many areas including algebra and combinatorics. A celebrated result of Hadwiger asserts that the intrinsic volumes constitute a basis for the continuous and rigid-motion invariant valuations on convex bodies and, moreover, this basis is distinguished by nonnegativity- and monotonicity properties. This is a quite complete and mathematically appealing situation for general convex bodies.

In the discrete setting (i.e. lattice polytopes), discrete volume (i.e.counting lattice points) takes the place of the volume. But whereas the structure of the space of lattice-invariant valuations on lattice polytopes parallels the continuous situation above quite remarkably, our understanding of nonnegative and monotone valuations is simply unsatisfactory. Even worse, the nonnegativity and monotonicity of the mixed volumes is genuinely lost for the discrete mixed volumes.

In this talk I will advocate a combinatorial theory of nonnegative, monotone, and mixed valuations. In the continuous case, this underlines the prominent role played by volume and recovers the classical mixed volumes. For lattice polytopes, we obtain a Hadwiger-type theorem and we show that our notion of combinatorial mixed valuation preserves nonnegativity and monotonicity for many valuations including the discrete volume. I will emphasize the strong ties to the combinatorics of subdivisions of (lattice) polytopes and, if time permits, I will remark on applications to recent results of DiRocco, Haase, and Nill on the (motivic) arithmetic genus. The talk is based on joint work with Katharina Jochemko.

11:00-12:00 Marianne Akian

Title: Majorization inequalities for valuations of eigenvalues

Abstract: In his work on the Graeffe method, Ostrowski obtained estimates of the moduli of the roots of a complex polynomial. These estimates can now be interpreted as majorization inequalities relating the log of the moduli of the roots of this polynomial with the roots of a tropicalized polynomial. Moreover, they are related to metric estimates for amoebas.

We show that this carries over to the eigenvalue problem: the valuations of the eigenvalues of a matrix, and more generally of a matrix polynomial, still satisfy majorization inequalities, involving now tropical eigenvalues. We also show estimates for the moduli of the eigenvectors and for the condition numbers of eigenvalues. Diagonal matrix scalings are an essential ingredient of the proof, which are also useful in applications to numerical eigenvalue computations, as they improve the condition numbers of eigenvalues. We also show similar inequalities for matrices over the field of Puiseux series with its non-archimedean valuation. This talk covers a series of works with Ravindra Bapat, Stéphane Gaubert, Andrea Marchesini, Meisam Sharify, and a current work with Francoise Tisseur.

14:00-15:00 Thorsten Theobald

Title: Conic stability of polynomials

Abstract: We introduce and study the notion of conic stability of multivariate polynomials in C[z_1, …, z_n], which naturally generalizes the stability of multivariate polynomials. The notion has its origin in the study of amoebas and imaginary projections, and the usual stability refers to the specific polyhedral cone R_+^n.

In particular, we generalize Borcea's and Brändén's multivariate version of the Hermite-Kakeya-Obreschkoff Theorem to the conic stability and provide a characterization for general as well as for polyhedral cones in terms of a directional Wronskian. And we generalize a major criterion for stability of determinantal polynomials to stability with respect to the positive semidefinite cone.

Joint work with Thorsten Jörgens.

15:30-16:30 Benjamin Schröter

Title: Rays in the Moduli Space of Tropical Linear Spaces

Abstract: Classically the Grassmannian over some field is the moduli space of d-dimensional linear subspaces in n-dimensional space. Its tropicalization yields a pure fan which only depends on the characteristic of the underlying field. As a set the tropical Grassmannian is contained in the Dressian, i.e., the moduli space of all tropical linear spaces. The Dressian is the non-pure subfan of matroidal subdivisions in the secondary fan of the hypersimplex. The relation of these fans is a field of active research.  

In this talk we present constructions for rays in the Dressian that highlight the differences of Grassmannians and the Dressian. Our main construction is derived from a new class of matroids, that we call split matroids. A split is a subdivision into two maximal cells and correspond also to rays of the Dressian. Moreover we enumerate a more general class of subdivisions, namely all multisplits, of the hypersimplex, which yields a connection two nested matroids and subdivisions of products of simplices. Partially joint work with Michael Joswig.



9:30-10:30 Michael Joswig

Title: Monomial tropical cones for multicriteria optimization

Abstract: We present an algorithm to compute all n nondominated points of a multicriteria discrete optimization problem with d objectives using at most $O(n^{\lfloor d/2 \rfloor})$ scalarizations. The method is similar to an algorithm by Klamroth et al. (2015) with the same complexity. As a difference, our method employs a tropical convex hull computation, and it exploits a particular kind of duality which is special for the tropical cones arising. This duality can be seen as a generalization of the Alexander duality of monomial ideals.

Joint work with Georg Loho.

11:00-12:30 Open problem session

14:00-15:00 Jens Forsgård

Title: Defective Dual Varieties for Real Spectra

Abstract: We introduce an invariant of a finite point configuration $A \subset \mathbb{R}^{1+n}$ which we denote the cuspidal form of A. We use this invariant to extend Esterov’s characterization of dual defective point configurations to exponential sums; the dual variety associated to A has codimension at least 2 if and only if A does not contain any iterated circuit. We discuss the case n=2 in detail, including a relationship with the study of self-dual toric varieties.

15:30-16:30 Bo Lin

Title: Linear and Rational Factorization of Tropical Polynomials

Abstract: The factorization of tropical polynomials is already an NP-Complete problem for bivariate ones. In this work we give an efficient algorithm for factorization and rational factorization of a rich class of homogeneous tropical polynomials in n variables. Special families of these polynomials have appeared in economics, discrete convex analysis, and combinatorics. Our theorems rely on an intrinsic characterization of regular mixed subdivisions of integral polytopes, and lead to many open problems of interest in discrete geometry. This is a joint work with Ngoc Mai Tran.



9:30-10:30 Alicia Dickenstein

Title: A bit of tropical varieties, a bit of polytopes

Abstract: I will present joint work with Bernard Mourrain and Maria Isabel Herrero on the tropicalization of generic rational varieties via curve valuations. We (slightly) extend results by Sturmfels, Tevelev and Yu, but our point of view can be generalized to deal with non-generic parametrizations. In the case of a generic rational hypersurface S, we give combinatorial conditions on the relative positions of the Newton polytopes of the polynomials defining the parametrization to determine the degree and the order of singularity of S at the origin. Some of these conditions look similar to those presented recently by Bihan and Soprunov, but they are different.

11:00-12:00 Marvin Hahn 

Title: Tropicalized quartics and canonical embeddings for tropical curves of genus 3

Abstract: Brodsky, Joswig, Morrison and Sturmfels showed that not all abstract tropical curves of genus 3 can be realized as a tropicalization of a quartic in the euclidean plane. In this talk, we focus on the interior of the maximal cones in the moduli space and classify all curves which can be realized as a faithful tropicalization in a tropical plane. Reflecting the algebro-geometric world, we show that these are exactly those which are not realizably hyperelliptic.

Our approach is constructive: For any not realizably hyperelliptic curve, we explicitly construct a realizable model of the tropical plane and a faithfully tropicalized quartic in it. These constructions rely on modifications resp. tropical refinements. Conversely, we prove that any realizably hyperelliptic curve cannot be embedded in such a fashion. For that, we rely on the theory of tropical divisors and embeddings from linear systems, and recent advances in the realizability of sections of the tropical canonical divisor. This is joint work with Hannah Markwig, Yue Ren and Ilya Tyomkin.

14:00-15:00 Jorge Alberto Olarte

Title: The Moduli Space of Harnack Curves in Toric Surfaces

Abstract: Harnack curves are a special family of plane algebraic curves which are characterized by having amoebas that behave in the simplest possible way. In this talk we will see how that allows us to compute the moduli space of Harnack curves with a given Newton polygon. We will show how this space can be embedded into the moduli space of pointed tropical curves. Through this embedding the moduli space of Harnack curves has a compactification which essentially is the secondary polytope of the Newton polygon. We present how this compactification is related to Viro’s patchworking of real algebraic curves.

15:30-16:30 Anton Leykin

Title: Beyond Polyhedral Homotopies

Abstract: We present an algorithmic framework which utilizes tropical geometry and homotopy continuation for solving systems of polynomial equations where some of the polynomials are generic elements in linear subspaces of the polynomial ring. This approach generalizes the polyhedral homotopies by Huber and Sturmfels. (Joint work with Josephine Yu)



9:30-10:30 Sandra di Rocco

Title: Higher order Gauss maps for lattice configurations

Abstract: A finite set of lattice points defines an embedded toric variety. The Gauss map represents a classical and powerful tool in projective geometry. Gauss maps of smooth non linear embeddings enjoy the nice property of being birational. I will define higher order Gauss mapps capturing higher osculating properties of the embedding and show that similar finiteness properties hold. For toric embeddings, defined by lattice configurations, these maps can be characterised by associated lattice configurations (and polytopes). This combinatorial setting imposes birationality fully generalizing the classical result. The talk is based on joint work with K. Jabbusch and A. Lundman.

11:00-11:40 Dima Grigoriev

Title: Tropical Combinatorial Nullstellensatz and Sparse Polynomials

Abstract: We give tropical analogues of

1. the combinatorial Nullstellensatz due to N. Alon and of Risler-Ronga conjecture;

2. Schwartz-Zippel lemma providing an exact bound on the number of points in a finite grid at which a polynomial of a fixed degree can vanish;

3. a universal testing set for sparse polynomials (for classical polynomials constructed by Grigoriev-Karpinski and Ben-Or-Tiwari);

4. Shub-Smale τ-conjecture.

These results were obtained jointly with V. Podolskii.

Also a polynomial complexity algorithm is designed for recognizing a tropical linear variety.

11:50-12:30 Dima Grigoriev

14:00-15:00 Stéphane Gaubert

Title: Condition numbers in nonarchimedean semidefinite programming and their relation with stochastic mean payoff games

Abstract: Semidefinite programming consists in optimizing a linear form over a spectrahedron, the latter being a cross section of the cone of positive semidefinite matrices. This makes sense over any real closed field, and in particular, over fields of real Puiseux series, equipped with their non archimedean valuation. In this way, a tropical spectrahedron can be defined as the image by the valuation of a nonarchimedean spectrahedron. The nonarchimedean semidefinite feasibility problem, with generic valuations of the input matrices, turns out to be equivalent to stochastic mean payoff games with perfect information. Solving the latter is a known problem in algorithmic game theory. It has an unsettled complexity, but a number of experimentally efficient algorithms have been developed. We used such stochastic games algorithms to solve generic nonarchimedean semidefinite problems.

We will show that, conversely, one can infer complexity bounds for stochastic games from their tropical formulation. To do so, we develop a metric geometry approach of nonarchimedean semidefinite programming. We use the value of a stochastic mean payoff game to define a nonarchimedean condition number. The latter measures the distance to unfeasibility, for a feasible instance, and vice versa. This condition number coincides with the inverse of the maximal radius of a ball included in the primal or dual feasible set. Here, the radius is measured in Hilbert's projective metric, the canonical metric of tropical convexity. The time needed to decide the winner of a stochastic mean payoff game can be bounded in terms of the condition number and of an auxiliary metric estimate. In this way, we obtain parametrized complexity bounds for several classes of games. 

The results of the first part of the talk, on tropical spectrahedra, are taken from a joint work with Allamigeon and Skomra, see arXiv:1603.06916 (in J. Symb. Comp.), arXiv:1610.06746 and arXiv:1801.02089. The results on nonarchimedean conditions numbers are from a current work with Allamigeon, Katz, and Skomra.

15:30-16:30 Timo de Wolff

Title: The Lattice of Amoebas

Abstract: We study amoebas of exponential sums as functions of their support set A. To any amoeba, we associate a set of approximating sections of amoebas, which we call caissons. We show that a bounded modular lattice of subspaces of a certain vector space induces a lattice structure on the set of caissons. Our results unifies the theories of lopsided amoebas and amoebas of exponential sums. As an application, we show that our theory of caissons yields improved certificates for existence of certain components of the complement of an amoeba. This is joint work with Jens Forsgård.



9:30-10:30 Alexander Esterov

Title: Galois theory for systems of equations, and small polytopes

Abstract: The classical Abel--Ruffini theorem claims that the general formula, expressing the roots of a polynomial in terms of its coefficients, exists only for polynomials of degree at most 4, i.e. the ones whose (1-dimensional) Newton polytope has volume at most 4.  We present the multidimensional version of it: the classification of general systems of polynomial equations solvable by radicals reduces to the classification of lattice polytopes of mixed volume 4, which we also prove to be finite in an appropriate sense. More generally, we obtain results on the monodromy of systems of polynomial equations, parallel to the recent results by Sottile and White for the monodromy of enumerative problems in Schubert calculus.

The proof is based on the analysis of the discriminants and defectivity of systems of polynomial equations, generalizing recent results by Borger and Nill. We also survey some of the many natural open questions at this interface between lattice polytopes, finite group theory and toric differential geometry.

11:00-12:00 Christian Haase

Title: The Kingman Coalescent as a Density on a Space of Trees

Abstract: Randomly pick n individuals from a population and look at their genealogy. The Kingman n-coalescent is a probabilistic model for the tree one obtains this way. It can be described by a probability density function on the space of equidistant trees with its fine fan structure, given by the Bergman fan of the complete graph.

I will describe this density and report on work in future with Lena Walter about relations of population genetics and algebraic geometry via the tropical connection.