Research
Areas of interest
(Discrete) Optimization, Polyhedral Geometry, Algorithmic Structures, Computational Complexity, Tropical Geometry, Discrete Geometry, Matroids
Publications

Tropical Ehrhart Theory and Tropical Volume
with Matthias Schymura
(publication)(arxiv)(slides)
Research in the Mathematical Sciences, 7(30) (2020)
Abstract
We introduce a novel intrinsic volume concept in tropical geometry. This is achieved by developing the foundations of a tropical analog of lattice point counting in polytopes. We exhibit the basic properties and compare it to existing measures. Our exposition is complemented by a brief study of arising complexity questions.
Matching fields and lattice points of simplices
with Ben Smith (publication)(arxiv)(slides)
Advances in Mathematics, 370 (2020), 107232
Abstract
We show that the Chow covectors of a linkage matching field define a bijection between certain degree vectors and lattice points, and we demonstrate how one can recover the linkage matching field from this bijection.
This resolves two open questions from Sturmfels and Zelevinsky (1993) on linkage matching fields. For this, we give an explicit construction that associates a bipartite incidence graph of an ordered partition of a common set to each lattice point in a dilated simplex.
Given a triangulation of a product of two simplices encoded by a set of spanning trees on a bipartite node set, we similarly prove that the bijection from left to right degree vectors of the trees is enough to recover the triangulation. As additional results, we show a cryptomorphic description of linkage matching fields and characterise the flip graph of a linkage matching field in terms of its prodsimplicial flag complex. Finally, we relate our findings to transversal matroids through the tropical Stiefel map.
Abstract tropical linear programming
(publication)(arxiv)
The Electronic Journal of Combinatorics, P2.51 (2020)
Abstract
In this paper we develop a combinatorial abstraction of tropical linear programming. This generalizes the search for a feasible point of a system of minplusinequalities. We obtain an algorithm based on an axiomatic approach to this generalization. It builds on the introduction of signed tropical matroids based on the polyhedral properties of triangulations of the product of two simplices and the combinatorics of the associated set of bipartite graphs with an additional sign information. Finally, we establish an upper bound for our feasibility algorithm applied to a system of minplusinequalities in terms of the secondary fan of a product of two simplices. The appropriate complexity measure is a shortest integer vector in a cone of the secondary fan associated to the system.
Signed tropical convexity
with László A. Végh (publication)(arxiv)(slides)
11th Innovations in Theoretical Computer Science Conference (ITCS 2020), LIPIcs, Volume 151 (2020), pp. 24:124:35
Abstract We establish a new notion of tropical convexity for signed tropical numbers. We provide several equivalent descriptions involving balance relations and intersections of open halfspaces as well as the image of a union of polytopes over Puiseux series and hyperoperations. Along the way, we deduce a new Farkas lemma and FourierMotzkin elimination without the nonnegativity restriction on the variables. This leads to a MinkowskiWeyl theorem for polytopes over the signed tropical numbers.
Monomial tropical cones for multicriteria optimization
with Michael Joswig (publication)(arxiv)(slides)
SIAM J. Discrete Math., 34(2) (2020), 11721191.
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 algorithms by Przybylski, Gandibleux, and Ehrgott and by Klamroth, Lacour, and Vanderpooten 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.
Linear Programs and Convex Hulls Over Fields of Puiseux Fractions
with Michael Joswig, Benjamin Lorenz, Benjamin Schröter (publication)
Mathematical Aspects of Computer and Information Sciences: 6th International Conference (MACIS 2015), Revised Selected Papers, LNCS Volume 9582 (2016), pp 429445
Abstract We describe the implementation of a subfield of the field of formal Puiseux series in polymake. This is employed for solving linear programs and computing convex hulls depending on a real parameter. Moreover, this approach is also useful for computations in tropical geometry.
Weighted digraphs and tropical cones
with Michael Joswig
(publication)
Linear Algebra Appl. 501 (2016), 304343.
Abstract
This paper is about the combinatorics of finite point configurations in the tropical projective space or, dually, of arrangements of finitely many tropical hyperplanes. Moreover, arrangements of finitely many tropical halfspaces can be considered via coarsenings of the resulting polyhedral decompositions of R^d. This leads to natural cell decompositions of the tropical projective space TP_min^(d1). Our method is to employ a known class of ordinary convex polyhedra naturally associated with weighted digraphs. This way we can relate to and use results from combinatorics and optimization. One outcome is the solution of a conjecture of Develin and Yu (2007).
MatchTheNet  An Educational Game on 3Dimensional Polytopes
with Michael Joswig, Benjamin Lorenz, Rico Raber (publication)(game homepage)
33rd International Symposium on Computational Geometry (SoCG 2017), LIPIcs, Volume 77 (2017), pp 66:166:5
Abstract We present an interactive game which challenges a single player to match 3dimensional polytopes to their planar nets. It is open source, and it runs in standard web browsers.
Preprints
Patchworking Oriented Matroids
with Marcel Celaya, Chi Ho Yuen (arxiv)
Abstract
In a previous work, we gave a construction of (not necessarily realizable) oriented matroids from a triangulation of a product of two simplices. In this followup paper, we use a variant of Viro's patchworking to derive a topological representation of the oriented matroid directly from the polyhedral structure of the triangulation, hence finding a combinatorial manifestation of patchworking besides tropical algebraic geometry. We achieve this by rephrasing the patchworking procedure as a controlled cell merging process, guided by the structure of tropical oriented matroids. A key insight is a new promising technique to show that the final cell complex is regular.
Oriented Matroids from Triangulations of Products of Simplices
with Marcel Celaya, Chi Ho Yuen (arxiv)
Abstract
We introduce a construction of oriented matroids from a triangulation of a product of two simplices. For this, we use the structure of such a triangulation in terms of polyhedral matching fields. The oriented matroid is composed of compatible chirotopes on the cells in a matroid subdivision of the hypersimplex, which might be of independent interest. In particular, we generalize this using the language of matroids over hyperfields, which gives a new approach to construct matroids over hyperfields. A recurring theme in our work is that various tropical constructions can be extended beyond tropicalization with new formulations and proof methods.
Tropical Carathéodory with Matroids
with Raman Sanyal (arxiv)
Abstract
Bárány's colorful generalization of Carathéodory's Theorem combines geometrical and combinatorial constraints. KalaiMeshulam (2005) and Holmsen (2016) generalized Bárány's theorem by replacing color classes with matroid constraints. In this note, we obtain corresponding results in tropical convexity, generalizing the tropical colorful Carathéodory Theorem of GaubertMeunier (2010). Our proof is inspired by geometric arguments and is reminiscent of matroid intersection. In particular, we show that the topological approach fails in this setting. We also discuss tropical colorful linear programming and show that it is NPcomplete. We end with thoughts and questions on generalizations to polymatroids, antimatroids as well as examples and matroid simplicial depth.
Face posets of tropical polyhedra and monomial ideals
with Ben Smith (arxiv)
Abstract
We exhibit several posets arising from commutative algebra, order theory, tropical convexity as potential face posets of tropical polyhedra, and we clarify their inclusion relations. We focus on monomial tropical polyhedra, and deduce how their geometry reflects properties of monomial ideals. Their vertexfacet lattice is homotopy equivalent to a sphere and encodes the Betti numbers of an associated monomial ideal.
Thesis
Doctoral Thesis “Combinatorics of Tropical Linear Programming”
(
publication)(
slides)
Abstract
The main topic of this work is the study of systems of inequalities where only the operations 'min' and '+' are used and which we call tropical linear inequality systems. An important algorithmic problem is to determine a point which fulfills all the inequalities. This problem, referred as the tropical feasibility problem, occurs in connection with scheduling as well as mean payoff games. It is analogous with the classical feasibility problem for linear inequality systems.
We study these systems by means of sets of bipartite graphs. Methods from combinatorial optimization yield a characterization of these bipartite graphs, referred as covector graphs, in terms of minimal matchings.
We start with a thorough investigation of polyhedra, which are naturally associated to shortest paths in weighted directed graphs.
It leads to new covector decompositions of the tropical projective space. We reveal the connection with order polytopes and the boundary of the tropical projective space. Furthermore, we resolve a conjecture of Develin and Yu (2007).
A second approach to examine tropical linear inequality systems arises by representing them as images of linear inequality systems over Puiseux series under a valuation map. We introduce the subfield of Puiseux fractions which is suitable for computations on a computer in contrast to Puiseux series, and we relate linear inequality systems over Puiseux fractions with linear inequality systems over the real numbers.
Combining these ideas from classical halfspace arrangements with the covector decompositions leads to an abstraction in terms of signed tropical matroids which are an analogue of classical oriented matroids. This allows us to study tropical linear inequality systems with tools for polyhedral subdivisions. While tropical linear inequality systems correspond to regular subdivisions of subpolytopes of the product of two simplices, our arguments readily apply to not necessarily regular subdivisions as well. We design an algorithm to determine the feasibility of a tropical linear inequality system which also works for the generalized structure derived from not necessarily regular subdivisions.
For regular subdivisions, the complexity is bounded by the entries of a minimal integer vector in a cone of the secondary fan of the product of two simplices.
Posters
 Poster for 7ECM (July 18 – 22, 2016)
 Poster for Einstein Workshop Discrete Geometry and Topology (March 1316, 2018)