Weighted digraphs and tropical cones

2015/03/31 by Michael Joswig, Georg Loho · 2 citations
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Class (philosophy) #Coding theory and cryptography #Combinatorics #Computer science #Conjecture #Discrete mathematics #Hyperplane #Mathematics #Polyhedron #Polynomial and algebraic computation #Projective space #Projective test #Pure mathematics #Regular polygon #Space (punctuation) #Tropical geometry #math.CO #msc:05C20 #msc:14T05 #msc:52B12

paper · pdf · doi:10.1016/j.laa.2016.02.027

published as Linear Algebra and its Applications, Volume 501, 15 July 2016, Pages 304-343 · 40 pages, 16 figures. Final version, journal information

openalex publication_date 2016/03/30 · arxiv created 2019/06/20 · arxiv updated 2019/06/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

This paper is about the combinatorics of finite point configurations in the tropical projective space or, dually, of arrangements of finitely many tropical hyperplanes. Moreover, arrangements of finitely many tropical halfspaces can be considered via coarsenings of the resulting polyhedral decompositions of ℝ^d. This leads to natural cell decompositions of the tropical projective space \mathbbTP_min^d-1. Our method is to employ a known class of ordinary convex polyhedra naturally associated with weighted digraphs. This way we can relate to and use results from combinatorics and optimization. One outcome is the solution of a conjecture of Develin and Yu (2007).

Citations

• TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES
• Computing the Vertices of Tropical Polyhedra Using Directed Hypergraphs
• Generating All Vertices of a Polyhedron Is Hard
• A strong-connectivity algorithm and its applications in data flow analysis
• Maximum-Minimum Sätze über Graphen
• Enumerating Polytropes

Cited by

• Tropical Geometry and Mechanism Design
• Tropical convex hulls of polyhedral sets