Home > Research > Publications & Outputs > On complete classes of valuated matroids

Research

Associated organisational units

Electronic data

  • main

    Accepted author manuscript, 688 KB, PDF document

    Available under license: CC BY: Creative Commons Attribution 4.0 International License

Links

Text available via DOI:

View graph of relations

On complete classes of valuated matroids

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

On complete classes of valuated matroids. / Husic, Edin; Loho, Georg; Smith, Ben et al.
In: TheoretiCS, Vol. 3, 10755, 18.11.2024.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Husic, E, Loho, G, Smith, B & Vegh, LA 2024, 'On complete classes of valuated matroids', TheoretiCS, vol. 3, 10755. https://doi.org/10.48550/arXiv.2107.06961, https://doi.org/10.46298/theoretics.24.24

APA

Husic, E., Loho, G., Smith, B., & Vegh, L. A. (2024). On complete classes of valuated matroids. TheoretiCS, 3, Article 10755. https://doi.org/10.48550/arXiv.2107.06961, https://doi.org/10.46298/theoretics.24.24

Vancouver

Husic E, Loho G, Smith B, Vegh LA. On complete classes of valuated matroids. TheoretiCS. 2024 Nov 18;3:10755. doi: 10.48550/arXiv.2107.06961, 10.46298/theoretics.24.24

Author

Husic, Edin ; Loho, Georg ; Smith, Ben et al. / On complete classes of valuated matroids. In: TheoretiCS. 2024 ; Vol. 3.

Bibtex

@article{b74b503e51eb41cc8e9110fd863ac9b9,
title = "On complete classes of valuated matroids",
abstract = "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.",
author = "Edin Husic and Georg Loho and Ben Smith and Vegh, {Laszlo A.}",
year = "2024",
month = nov,
day = "18",
doi = "10.48550/arXiv.2107.06961",
language = "English",
volume = "3",
journal = "TheoretiCS",

}

RIS

TY - JOUR

T1 - On complete classes of valuated matroids

AU - Husic, Edin

AU - Loho, Georg

AU - Smith, Ben

AU - Vegh, Laszlo A.

PY - 2024/11/18

Y1 - 2024/11/18

N2 - 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.

AB - 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.

U2 - 10.48550/arXiv.2107.06961

DO - 10.48550/arXiv.2107.06961

M3 - Journal article

VL - 3

JO - TheoretiCS

JF - TheoretiCS

M1 - 10755

ER -