TY - JOUR
T1 - Tropical Carathéodory with Matroids
AU - Loho, Georg
AU - Sanyal, Raman
N1 - Funding Information:
This work started during the program Tropical Geometry, Amoebas and Polytopes at the Institute Mittag-Leffler in spring 2018. The authors would like to thank the institute as well as the organizers for the inspiring atmosphere. We would also like to thank Andreas Holmsen, Diane Maclagan, Sebastian Manecke, Frédéric Meunier, Matthias Schymura, Bilal Sheikh, and Ben Smith for insightful conversations. GL was supported by the European Research Council (ERC) Starting Grant ScaleOpt, No. 757481. We thank an anonymous reviewer for careful reading and helpful comments that led to a strengthening of the results and an improved exposition.
Publisher Copyright:
© 2022, The Author(s).
PY - 2023/1
Y1 - 2023/1
N2 - Bárány’s colorful generalization of Carathéodory’s Theorem combines geometrical and combinatorial constraints. Kalai–Meshulam (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 Gaubert–Meunier (2010). Our proof is inspired by geometric arguments and is reminiscent of matroid intersection. Moreover, we show that the topological approach fails in this setting. We also discuss tropical colorful linear programming and show that it is NP-complete. We end with thoughts and questions on generalizations to polymatroids, anti-matroids as well as examples and matroid simplicial depth.
AB - Bárány’s colorful generalization of Carathéodory’s Theorem combines geometrical and combinatorial constraints. Kalai–Meshulam (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 Gaubert–Meunier (2010). Our proof is inspired by geometric arguments and is reminiscent of matroid intersection. Moreover, we show that the topological approach fails in this setting. We also discuss tropical colorful linear programming and show that it is NP-complete. We end with thoughts and questions on generalizations to polymatroids, anti-matroids as well as examples and matroid simplicial depth.
KW - Colorful Carathéodory Theorem
KW - Matroid Carathéodory Theorem
KW - Tropical convex geometry
KW - UT-Hybrid-D
UR - http://www.scopus.com/inward/record.url?scp=85141402306&partnerID=8YFLogxK
U2 - 10.1007/s00454-022-00446-0
DO - 10.1007/s00454-022-00446-0
M3 - Article
AN - SCOPUS:85141402306
VL - 69
SP - 139
EP - 155
JO - Discrete and computational geometry
JF - Discrete and computational geometry
SN - 0179-5376
IS - 1
ER -