Edin Husić ; Georg Loho ; Ben Smith ; László A. Végh - On complete classes of valuated matroids

theoretics:10755 - TheoretiCS, November 18, 2024, Volume 3 - https://doi.org/10.46298/theoretics.24.24
On complete classes of valuated matroidsArticle

Authors: Edin Husić ORCID; Georg Loho ORCID; Ben Smith ORCID; László A. Végh ORCID

    We characterize a rich class of valuated matroids, called 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. We exhibit a family of valuated matroids that are not R-minor based on sparse paving matroids. 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 (Theoretical Economics 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.


    Volume: Volume 3
    Published on: November 18, 2024
    Accepted on: July 21, 2024
    Submitted on: December 29, 2022
    Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics,Computer Science - Computer Science and Game Theory,Mathematics - Optimization and Control

    Consultation statistics

    This page has been seen 104 times.
    This article's PDF has been downloaded 60 times.