Publications (pdf)

- Valuative invariants for large classes of matroids with Luis Ferroni
in Journal of the London Mathematical Society, Volume 110(3) (2024), e12984
We study an operation in matroid theory that allows to transition a given matroid into another with more bases via relaxing a “stressed subset”. This provides a framework in which we obtain a new combinatorial characterization of the class of elementary split matroids, which is expected to be asymptotically predominant. Moreover, it enables to describe an explicit matroid subdivision of a hypersimplex, which in turn can be used to write down explicit formulas for the evaluations of any valuative invariant on these matroids. This shows that evaluations depend solely on the behavior of the invariant on a well-behaved small subclass of Schubert matroids that we call “cuspidal matroids”. Along the way, we make a comprehensive summary of the tools and methods one might use to prove that an invariant is valuative, and we use them to provide new proofs of the valuativeness of several invariants. We address systematically the consequences of our approach for a comprehensive list of invariants. They include the volume and Ehrhart polynomial of base polytopes, the Tutte polynomial, Kazhdan–Lusztig polynomials, the Whitney numbers of the first and second kind, spectrum polynomials and a generalization of these by Denham, chain polynomials and Speyer’s g-polynomials, as well as Chow rings of matroids and their Hilbert–Poincaré series. The flexibility of this setting allows us to give a unified explanation for several recent results regarding the listed invariants; furthermore, we emphasize it as a powerful computational tool to produce explicit data and concrete examples.
- Massively parallel computation of tropical varieties, their positive part, and tropical Grassmannians with D. Bendle, J. Böhm and Y. Ren
in Journal of Symbolic Computation. Special Issue: MEGA 2022 120 (2024), 102224
Massively parallel computation of tropical varieties, their positive part, and tropical Grassmannians
We present a massively parallel framework for computing tropicalizations of algebraic varieties which can make use of symmetries using the workflow management system GPI-Space and the computer algebra system Singular. We determine the tropical Grassmannian TGr0(3,8). Our implementation works efficiently on up to 840 cores, computing the 14763 orbits of maximal cones under the canonical S8-action in about 20 minutes. Relying on our result, we show that the Gröbner structure of TGr0(3,8) refines the 16-dimensional skeleton of the coarsest fan structure of the Dressian Dr(3,8), except for 23 orbits of special cones, for which we construct explicit obstructions to the realizability of their tropical linear spaces. Moreover, we propose algorithms for identifying maximal-dimensional cones which belong to positive tropicalizations of algebraic varieties. We compute the positive Grassmannian TGr+(3,8) and compare it to the cluster complex of the classical Grassmannian Gr(3,8).
- The Merino-Welsh Conjecture for split matroids with Luis Ferroni
in Annals of Combinatorics 27(3) (2023), 737–748
The Merino-Welsh Conjecture for split matroids
In 1999 Merino and Welsh conjectured that evaluations of the Tutte polynomial of a graph satisfy an inequality. In this short article we show that the conjecture generalized to matroids holds for the large class of all split matroids by exploiting the structure of their lattice of cyclic flats. This class of matroids strictly contains all paving and copaving matroids.
- Parametric shortest-path algorithms via tropical geometry with Michael Joswig
in Mathematics of Operations Research 47(3) (2022), 2065–2081
Parametric shortest-path algorithms via tropical geometry
We study parameterized versions of classical algorithms for computing shortest-path trees. This is most easily expressed in terms of tropical geometry. Applications include shortest paths in traffic networks with variable link travel times.
- Ehrhart polynomials of rank two matroids with Luis Ferroni and Katharina Jochemko
in Advances in Applied Mathematics 141 (2022), 102410, 26 pages
Over a decade ago De Loera, Haws and Köppe conjectured that Ehrhart polynomials of matroid polytopes have only positive coefficients. This intensively studied conjecture has recently been disproved by the first author who gave counterexamples of all ranks greater or equal to three. In this article we complete the picture by showing that Ehrhart polynomials of matroids of lower rank have indeed only positive coefficients. Moreover, we show that they are coefficient-wise bounded by the minimal and the uniform matroid.
- Correlation bounds for fields and matroids with June Huh and Botong Wang
in Journal of the European Mathematical Society 24 (2022), 1335–1351
Let G be a finite connected graph, and let T be a spanning tree of G chosen uniformly at random. The work of Kirchhoff on electrical networks can be used to show that the events e1∈T and e2∈T are negatively correlated for any distinct edges e1 and e2. What can be said for such events when the underlying matroid is not necessarily graphic? We use Hodge theory for matroids to bound the correlation between the events e∈B, where B is a randomly chosen basis of a matroid. As an application, we prove Mason's conjecture that the number of k-element independent sets of a matroid forms an ultra-log-concave sequence in k.
- Reconstructibility of matroid polytopes with Guillermo Pineda-Villavicencio
in SIAM Journal on Discrete Mathematics 36 (2022), 490–508
We specify what is meant when a polytope is reconstructible from its graph or dual graph, and introduce the problem of class reconstructibility, i.e., the (dual) graph of a polytope is unique within a given class of polytopes. We provide examples showing that cubical polytopes and matroid (base) polytopes are not reconstructible from either their graphs or their dual graphs. In fact, our counterexamples for matroid polytopes include hypersimplices. Furthermore, we prove that matroid polytopes are class reconstructible form their graphs, and we present a O(n3) algorithm that computes the vertices of a matroid polytope from its n-vertex graph. Additionally, our proof includes a characterisation of all matroids with isomorphic basis exchange graphs.
- Moduli spaces of codimension-one subspaces in a linear variety and their tropicalization with Philipp Jell, Hannah Markwig and Felipe Rincón
in Electronic Journal of Combinatorics 29(2) (2022), P2.31, 33 pages
Moduli spaces of codimension-one subspaces in a linear variety and their tropicalization
We study the moduli space of d-dimensional linear subspaces contained in a fixed (d+1)-dimensional linear variety X, and its tropicalization. We prove that these moduli spaces are linear subspaces themselves, and thus their tropicalization is completely determined by their associated (valuated) matroids. We show that these matroids can be interpreted as the matroid of lines of the hyperplane arrangement corresponding to X, and generically are equal to a Dilworth truncation of the free matroid. In this way, we can describe combinatorially tropicalized Fano schemes and tropicalizations of moduli spaces of stable maps of degree 1 to a plane.
- On local Dressians of matroids with Jorge Alberto Olarte and Marta Panizzut
in Algebraic and Geometric Combinatorics on Lattice Polytopes. Proceedings of the Summer Workshop on Lattice Polytopes, Osaka 2018 (2019), 309–329
We study the fan structure of Dressians Dr(d,n) and local Dressians Dr(M) for a given matroid M. In particular we show that the fan structure on Dr(M) given by the three term Plücker relations coincides with the structure as a subfan of the secondary fan of the matroid polytope P(M). As a corollary, we have that a matroid subdivision is determined by its 3-dimensional skeleton. We also prove that the Dressian of the sum of two matroids is isomorphic to the product of the Dressians of the matroids. Finally we focus on indecomposable matroids. We show that binary matroids are indecomposable, and we provide a non-binary indecomposable matroid as a counterexample for the converse.
- Multi-splits and tropical linear spaces from nested matroids
in Discrete & Computational Geometry 61.3 (2019), 661–685
Multi-splits and tropical linear spaces from nested matroids
In this paper we present an explicit combinatorial description of a special class of facets of the secondary polytopes of hypersimplices. These facets correspond to polytopal subdivisions called multi-splits. We show a relation between the cells in a multi-split of the hypersimplex and nested matroids. Moreover, we get a description of all multi-splits of a product of simplices. Additionally, we present a computational result to derive explicit lower bounds on the number of facets of secondary polytopes of hypersimplices.
- Algorithms for tight spans and tropical linear spaces with Simon Hampe and Michael Joswig
in Journal of Symbolic Computation. Special Issue: MEGA 2017 91 (2019), 116–128
Algorithms for Tight Spans and Tropical Linear Spaces
We describe a new method for computing tropical linear spaces and more general duals of polyhedral subdivisions. It is based on Ganter's algorithm (1984) for finite closure systems.
- The degree of a tropical basis with Michael Joswig
in Proceedings of the American Mathematical Society 146 (2018), 961–970
We give an explicit upper bound for the degree of a tropical basis of a homogeneous polynomial ideal. As an application f-vectors of tropical varieties are discussed. Various examples illustrate differences between Gröbner and tropical bases.
- Matroids from hypersimplex splits with Michael Joswig
in Journal of Combinatorial Theory Series A 151 (2017), 254–284
A class of matroids is introduced which is very large as it strictly contains all paving matroids as special cases. As their key feature these split matroids can be studied via techniques from polyhedral geometry. It turns out that the structural properties of the split matroids can be exploited to obtain new results in tropical geometry, especially on the rays of the tropical Grassmannians.
- Linear programs and convex hulls over fields of Puiseux fractions with Michael Joswig, Georg Loho and Benjamin Lorenz
in Lecture Notes in Computer Science, Mathematical Aspects of Computer and Information Sciences. MACIS 2015 – 6th International Conference (2016), 429–445
Linear Programs and Convex Hulls Over Fields of Puiseux Fractions
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.

Preprints

- Tutte polynomials of matroids as universal valuative invariants with Luis Ferroni
Tutte polynomials of matroids as universal valuative invariants
We provide a full classification of all families of matroids that are closed under duality and minors, and for which the Tutte polynomial is a universal valuative invariant. There are four inclusion-wise maximal families, two of which are the class of elementary split matroids and the class of graphic Schubert matroids. As a consequence of our framework, we derive new properties of Tutte polynomials of arbitrary matroids. Among other results, we show that the Tutte polynomial of every matroid can be expressed uniquely as an integral combination of Tutte polynomials of graphic Schubert matroids.
- Matroids in OSCAR with Daniel Corey and Lukas Kühne
Matroids in OSCAR
OSCAR is an innovative new computer algebra system which combines and extends the power of its four cornerstone systems - GAP (group theory), Singular (algebra and algebraic geometry), Polymake (polyhedral geometry), and Antic (number theory). Here, we present parts of the module handeling matroids in OSCAR, which will appear as a chapter of the upcoming OSCAR book. A matroid is a fundamental and actively studied object in combinatorics. Matroids generalize linear dependency in vector spaces as well as many aspects of graph theory. Moreover, matroids form a cornerstone of tropical geometry and a deep link between algebraic geometry and combinatorics. Our focus lies in particular on computing the realization space and the Chow ring of a matroid.
- Enumerating the faces of split matroid polytopes with Luis Ferroni
Enumerating the faces of split matroid polytopes
This paper initiates the explicit study of face numbers of matroid polytopes and their computation. We prove that, for the large class of split matroid polytopes, their face numbers depend solely on the number of cyclic flats of each rank and size, together with information on the modular pairs of cyclic flats. We provide a formula which allows us to calculate f-vectors without the need of taking convex hulls or computing face lattices. We discuss the particular cases of sparse paving matroids and rank two matroids, which are of independent interest due to their appearances in other combinatorial and geometric settings.

Thesis

- Matroidal subdivisions, Dressians and tropical Grassmannians
online publication DepositOnce (2018) at TU Berlin
Matroidal subdivisions, Dressians and tropical Grassmannians
In this thesis we study various aspects of tropical linear spaces and their moduli spaces, the tropical Grassmannians and Dressians. Tropical linear spaces are dual to matroid subdivisions. Motivated by the concept of splits, the simplest case of a subdivision, a new class of matroids is introduced, which can be studied via techniques from polyhedral geometry. This class is very large as it strictly contains all paving matroids. The structural properties of these split matroids can be exploited to obtain new results in tropical geometry, especially on the rays of the tropical Grassmannians and the dimension of the Dressian. In particular, a relation between matroid realizability and certain tropical linear spaces is elaborated. The rays of a Dressian correspond to facets of the secondary polytope of a hypersimplex. A special class of facets is obtained by a generalization of splits, called multi-splits or originally, in Herrmann’s work, k-splits. We give an explicit combinatorial description of all multi-splits of the hypersimplex. These are in correspondence to nested matroids and, via the tropical Stiefel map, also to multi-splits of products of simplices. Hence, we derive a description for all multi-splits of a product of simplices. Moreover, a computational result leads to explicit lower bounds on the total number of facets of secondary polytopes of hypersimplices. Other computational aspects are also part of our research: A new method for computing tropical linear spaces and more general duals of polyhedral subdivisions is developed and implemented in the software polymake. This is based on Ganter’s algorithm (1984) for finite closure systems. Additionally, we describe the implementation of a subfield of the field of formal Puiseux series. This is employed for solving linear programs and computing convex hulls depending on a real parameter. Moreover, this approach is useful for computations in convex and algebraic tropical geometry. Tropical varieties, as for example tropical linear spaces or tropical Grassmannians, are intersections of finitely many tropical hypersurfaces. The set of corresponding polynomials is a tropical basis. We give an explicit upper bound for the degree of a general tropical basis of a homogeneous polynomial ideal. As an application f-vectors of tropical varieties are discussed. Various examples illustrate differences between Gröbner bases and tropical bases.

Other Publications

- Dressians and tropical Grassmannians - Poster presented at MEGA2015
Dressians and tropical Grassmannians - Poster presented at MEGA2015
click on the picture
Poster Dressians and tropical Grassmannians
- The tropical Grassmannian TropGr(2,6) - Interactive model
The tropical Grassmannian TropGr(2,6) - Interactive model for the DGD Gallery
click on the picture
The tropical Grassmannian TropGr(2,6)
- 2048 - Article for Mitteilungen der DMV (german) with Antje Schulz
2048 - Article for Mitteilungen der DMV (german)
A short text about a poular application implemented by Gabriele Cirulli.

Software

I contributed to polymake and OSCAR

Download and other sources

Complete list of publications
according to MathSciNet
according to Zentralblatt MATH
according to Google Scholar
according to OCRID
according to dblp
according to scopus
according to arxiv