Workshop on Tropical algebra and applications

January 22 - 26, 2018

 

Week schedule

 

Monday

9:30-10:30 Felipe Rincon

Title: Tropical Ideals

Abstract: The past few years have seen a significant effort to give tropical geometry a solid algebraic foundation. In this talk I will introduce tropical ideals, which are ideals over the tropical semiring in which any bounded-degree piece is “matroidal”. I will discuss joint work with Diane Maclagan studying some of their main properties, and in particular showing that their underlying varieties are always finite polyhedral complexes.

11-12 Ngoc Tran

Title: Linear and rational factorization of tropical polynomials

Abstract: Already for bivariate tropical polynomials, factorization is an NP-Complete problem. In this paper, we give an efficient algorithm for factorization and rational factorization of a rich class of 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.

Joint work with Bo Lin.

14-15 Gregorio Malajovich

Title: Mixed volume computations, tropical varieties and quermassintegralen

Abstract: This talk is about solving certain sparse tropical polynomial systems. Those systems arise as the initial system for nonlinear homotopy in toric manifolds. The complexity analysis of the algorithm is done in terms of certain quermassintegrals, that generalize the mixed volume.

15:30-16:30 Jeff Sommars

Title: Algorithms and Software for Computing Tropical Prevarieties

Abstract: The computation of the tropical prevariety is the first step in the application of polyhedral methods to finding positive dimensional solution sets of polynomial systems. I’ll describe several algorithms that can be used to compute tropical prevarieties and also present a related software package. I'll conclude by reporting on several computational results, including the first computation of the tropical prevariety of the cyclic 16-roots problem.

 

Tuesday

9:30-10:30 Anders Jensen

Title: Finding binomials in polynomial ideals

Abstract: Deciding whether a polynomial ideal contains monomials is a key ingredient in algorithms for computing tropical varieties. It can be can done using usual Groebner basis techniques. Deciding if a polynomial ideal contains binomials is more complicated. Using projections and stable intersections in tropical geometry we show how the general case can be reduced to the case of zero-dimensional ideals. In the case of rational coefficients the zero-dimensional problem can then be solved via Ge's algorithm in number theory 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.

11-11:40 Jan Verschelde

Title: Polyhedral Methods to Solve Polynomial Systems I:
 computing pure dimensional solution sets

Abstract: In the zero dimensional case, polyhedral homotopies compute approximations for all isolated solutions of a polynomial system. The tropical variety provides candidate tropisms for the leading exponents of the power series expansions at the positive solution sets.
Our methods are illustrated on the cyclic n-roots problem. This talk is based on joint work with Danko Adrovic, Nathan Bliss, Anders Jensen, and Jeff Sommars.

11:50-12:30 Jan Verschelde

Title: Polyhedral Methods to Solve Polynomial Systems II:
 computing mixed dimensional solution sets

Abstract: In the mixed dimensional case, we consider polynomial systems which may have isolated solutions and solution sets of different dimensions. Solution sets are represented by power series expansions and computed by Newton's method. The reformulation of polyhedral homotopies with the application of a power series Newton's method will be sketched.
This talk is based on joint work with Danko Adrovic, Nathan Bliss, Anders Jensen, and Jeff Sommars.

14-15 Madeline Brandt

Title: Computing Berkovich Skeleta of Curves

Abstract: Given a smooth curve defined over a valued field, it is a difficult problem to compute the Berkovich skeleton of the curve. In theory, one can find a semistable model for the curve and then find the dual graph of the special fiber, and this will give the skeleton. Another option is to find an embedding of the curve such that the tropicalization is faithful. In practice, these procedures are not algorithmic and finding the correct model or embedding can be difficult. It is known how to find the Berkovich skeleton of genus one and genus two curves; more recently, the hyperelliptic case has also been solved. In this talk, we outline the problem and known progress, and present the solution for superelliptic curves y^n=f(x). 

15:30-16:30 Frederic Bihan

Title: Criteria for the strict monotonicity of mixed volumes of polytopes

Abstract: We give several necessary and sufficient conditions to have a strict inequality V(P_1,...,P_n) < V(Q_1,...,Q_n) between mixed volumes, where P_1, ..., P_n, Q_1, ..., Q_n are convex polytopes such that P_i is contained in Q_i. One such condition is given in terms of polyhedral subdivisions of Cayley polytopes, and generalizes the classical condition to have a non-zero mixed volume. As an interesting consequence, we get a generalization of Cramer's Rule for any polynomial system.

This is based on a joint work with E. Soprunov.

 

Wednesday

9:30-10:30 Emanuele Delucchi

Title: Some aspects of matroids over hyperfields

Abstract: Matroids over hyperfields, introduced by Baker and Bowler in 2016, offer a new unifying vision encompassing matroids, vector spaces, and related ideas in tropical geometry. The key tool are hyperfields, i.e., algebraic structures akin to fields — but with multivalued addition.

In this talk I will define matroids over hyperfields, present some examples (especially as related to tropical geometry and oriented matroids) and I will discuss some of the first results in this very young subject (which can be understood as looking for a “linear algebra” over hyperfields).

11-12 Kalina Mincheva

Title: Prime congruences and tropical Krull dimension

Abstract: We propose a definition for prime congruences which allows us to define Krull dimension of a semiring as the length of the longest chain of prime congruences. We give a complete description of prime congruences in the polynomial and Laurent polynomial semirings over the tropical semifield and the Boolean semifield. We show that the dimension of the polynomial and Laurent polynomial semiring over these idempotent semifields is equal to the number of variables plus the dimension of the ground semifield. We extend this result to all additively idempotent semirings. We show that using this notion of algebraic dimension we can recover the dimension of tropical varieties. 

14-15 Boulos El-Hilany

Title: Constructing polynomial systems with many positive solutions using tropical geometry

Abstract: The number of positive solutions to a system of two polynomials in two variables defined over the field of real numbers with a total of five distinct monomials cannot exceed 15. All previously known examples have at most 5 positive solutions. 

The main result presented in this talk is the construction of a system as above having 7 positive solutions. This is achieved using tools developed in tropical geometry. When the corresponding tropical hypersurfaces intersect transversally, one can easily estimate the positive solutions to the system using the classical combinatorial patchworking for complete intersections. I apply this generalization to construct a system as above having 6 positive solutions. I also show that this bound is sharp. Consequently, the main result is proved using non-transversal intersections of tropical curves.

15:30-16:30 Yoav Len

Title: Tropical dual varieties

Abstract: I will introduce the tropical dual variety, which similarly to the algebraic case, classifies tangent hyperplanes to a given variety.

As I will show, this object is indeed a tropical variety, and the construction commutes with tropicalization. As a result, we uncover combinatorial aspects of projective dual varieties, and ob- tain a recipe for computing their Newton polygon. This is joint work with Nathan Ilten.

 

Thursday

9:30-10:30 Xavier Allamigeon

Title: Log-barrier interior point methods are not strongly polynomial

Abstract: We prove that primal-dual log-barrier interior point methods are not strongly polynomial, by constructing a family of linear programs with 3r+1 inequalities in dimension 2r for which the number of iterations performed is in $\Omega(2^r)$. The total curvature of the central path of these linear programs is also exponential in r, disproving a continuous analogue of the Hirsch conjecture proposed by Deza, Terlaky and Zinchenko. Our method is to tropicalize the central path in linear programming. The tropical central path is the piecewise-linear limit of the central paths of parameterized families of classical linear programs viewed through logarithmic glasses. This allows us to provide combinatorial lower bounds for the number of iterations and the total curvature, in a general setting.

(Joint work with P. Benchimol, S. Gaubert, and M. Joswig)

11-11:40 Mark Kambites 

Title: The multiplicative structure of tropical matrices

Abstract: I will discuss the semigroup-theoretic structure of the n-by-n tropical matrices under multiplication, and how it relates to the geometry of tropical polytopes. The talk will assume minimal background knowledge in abstract algebra, and will seek to introduce (and motivate) the required semigroup-theoretic ideas from first principles. Original results presented (if we get that far!) will be based on joint work with Christopher Hollings, Zur Izhakian and Marianne Johnson.

11:50-12:30 Mark Kambites

14-15 Yue Ren

Title: Computing tropical varieties using Newton polygon methods

Abstract: We will discuss recent advances in the computation of tropical varieties from polynomial ideals. We start with a brief introduction of the original algorithm developed by Bogart, Jensen, Speyer, Sturmfels and Thomas. We then identify its bottlenecks, and compare various approaches to overcome them.

In particular, we will touch upon the work by Chan and Maclagan on computing tropical curves using projections and reconstructions, and another approach using Newton polygon methods and root approximation. This is joint work with Tommy Hofmann.

15:30-16:30 Elizabeth Baldwin

Title: Geometry in Consumer Preferences, Equilibrium and Auction Design

Abstract: This talk covers several papers in which we introduce techniques from tropical geometry into economics. Specifically, we gain new insights into the structure of consumer preferences when goods are indivisible, allowing a new system of classification that is both mathematically straightforward and economically meaningful. These insights in turn lead to new theorems on competitive equilibrium. And they allow us to extend the design of auctions in which multiple differentiated products are sold simultaneously -- auctions not only interesting in theory but also have already been put to real-world use.

 

Friday

9:30-10:30 Marianne Johnson

Title: Identities in upper triangular tropical matrix semigroups and the bicyclic monoid 

Abstract: This talk concerns some joint work with Laure Daviaud and Mark Kambites. We provide a necessary and sufficient condition for an identity to hold in the semigroup of n x n upper triangular tropical matrices, and use this result in the case n=2 to give a positive answer the question, posed by Izhakian and Margolis, of whether this semigroup satisfies the same identities as the bicyclic monoid.

11-12 Jan Draisma

Title: Tropical aspects of algebraic matroids

Abstract: Given a closed, irreducible variety X in K^E, where K is an algebraically closed field and E is a finite set, call a subset I of E independent if the projection X -> K^I is dominant. This gives a matroid M on E, and X is called an algebraic realisation of M. Tropical geometry can help us understand algebraic matroids via several different routes.

First, trop(X) determines M, and this has been useful in determining the matroid structure for certain varieties. Second, if char(K)=p>0, then X determines not only M but also a natural valuation of M that we dub the Lindström valuation. This extra data can sometimes be used to determine whether a given matroid N is algebraically realisable over K.

A sample theorem is the following: if N admits no nontrivial valuations, then N is algebraic over K if and only if it is linear over K.

(Joint work with Guus Bollen and Rudi Pendavingh.)