Tropical Carathéodory with Matroids

Area of Science:

• Tropical geometry
• Combinatorial geometry
• Convexity theory

Background:

• Bárány's colorful generalization of Carathéodory's Theorem integrates geometric and combinatorial constraints.
• Previous work generalized Bárány's theorem using matroid constraints, replacing color classes.
• The Tropical Colorful Carathéodory Theorem by Gaubert-Meunier (2010) established results in tropical convexity.

Purpose of the Study:

• To generalize Bárány's colorful theorem and its matroid extensions to the setting of tropical convexity.
• To explore the applicability of topological methods in this tropical context.
• To investigate the computational complexity of tropical colorful linear programming.

Main Methods:

• The study employs geometric arguments inspired by matroid intersection.
• It adapts concepts from colorful Carathéodory theorems and matroid theory to tropical convexity.
• Proof techniques are developed to address the unique properties of tropical convexity.

Main Results:

• New results are established for tropical convexity, generalizing the Tropical Colorful Carathéodory Theorem.
• It is shown that a direct topological approach, successful in other contexts, is not applicable here.
• Tropical colorful linear programming is proven to be NP-complete.

Conclusions:

• The findings provide a significant extension of colorful Carathéodory theorems into tropical convexity.
• The limitations of topological methods highlight the distinct nature of tropical geometric problems.
• The NP-completeness result has implications for the computational study of tropical optimization problems.