CIRM – Research in Pairs — Tropical Representations of Monoids and Matroids

Tropical matrices and their unique correspondence to weighted digraphs establish a main tool for algebraic representations and studying of combinatorial objects. With these representations sophisticated combinatorial and algorithmic aspects become transparent, making the theory more comprehensive and applicable. Tropical matrices have a very special behavior – they admit a nontrivial semigroup identity. This property is highly significant, and is carried over to any faithfully represented monoid, having direct implications in graph theory and automata theory.