Tropical Carathéodory with Matroids

Georg Loho*, Raman Sanyal

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

3 Downloads (Pure)


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.

Original languageEnglish
Pages (from-to)139-155
Number of pages17
JournalDiscrete and computational geometry
Issue number1
Early online date4 Nov 2022
Publication statusPublished - Jan 2023


  • Colorful Carathéodory Theorem
  • Matroid Carathéodory Theorem
  • Tropical convex geometry
  • UT-Hybrid-D


Dive into the research topics of 'Tropical Carathéodory with Matroids'. Together they form a unique fingerprint.

Cite this