Title: On complete classes of valuated matroids
| Speaker: | László Végh |
| Affiliation: | London School of Economics |
| Zoom: | Please email Emma Watson |
Abstract:
Valuated matroids were introduced by Dress and Wenzel in 1992. They are a central object in discrete convex analysis, and play important roles in other areas such as mathematical economics and tropical geometry. Finding a constructive characterization, i.e., showing that all valuated matroids can be derived from a simple class by some basic operations has been a natural question proposed in various contexts.
Motivated by this, we study the class of R-minor valuated matroids, that includes the indicator functions of matroids, and is closed under operations such as taking minors, duality, and induction by network. Our main result exhibits valuated matroids that are not R-minor, giving a negative answer to a question asked by Frank in 2003. Valuated matroids are inherently related to gross substitute valuations in mathematical economics. By the same token we refute the Matroid Based Valuation Conjecture by Ostrovsky and Paes Leme from 2015, asserting that every gross substitute valuation arises from weighted matroid rank functions by repeated applications of merge and endowment operations. Our result also has implications in the context of Lorentzian polynomials: it reveals the limitations of known construction operations.
This is joint work with Edin Husić, Georg Loho, and Ben Smith.