The Number of Tropical Order Types and Coherent Matching Fields
Abstract
We investigate counting problems for discrete (geometric) structures in tropical settings, motivated by the comparison of the expressivity of linear programs and mean-payoff games. First, we give an upper bound on the number of coherent matching fields of type (n,r) and a lower bound on the number of combinatorial types of n-hyperplane sequences in the max-plus tropical space of dimension r−1. These structures are closely related, and our bounds establish that as n → ∞, for every fixed r their number equals n(r−1)2n+o(n). This in turn implies that the number of regular triangulations of the products of simplices Δn−1×Δr−1 is also n(r−1)2n+o(n), thereby answering a question of Santos. Second, we obtain that the number of labeled order types over the reals and over the signed tropical numbers coincide at first order, establishing a comparison of the expressivity of mean-payoff games and linear programs as measured by labeled order types. Last, the subclass of mean-payoff games known as parity games arise from linear programs by a ``double tropicalization.'' We show that the number of labeled order types obtained after this double tropicalization collapses.
Related
- A Physically-Motivated Stochastic Model of Tropical Cyclone Dynamic Wind Fields
- Tuza's Ryser-conjecture claim for four-partite hypergraphs with matching number two
- Edge ideals of gapfree graphs with matching number $3$
- The maximum number of edges in minimal matching covered graphs
- Routing Optimality for Demand Graphs of Matching Number at Most Two
BibTeX
@misc{allamigeon2026number,
title = {{The Number of Tropical Order Types and Coherent Matching Fields}},
author = {Xavier Allamigeon and Yiyuan Chen and Stéphane Gaubert and Xavier Goaoc},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.40622},
eprint = {2610.40622},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.40622},
}
RIS
TY - UNPB
TI - The Number of Tropical Order Types and Coherent Matching Fields
AU - Xavier Allamigeon
AU - Yiyuan Chen
AU - Stéphane Gaubert
AU - Xavier Goaoc
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.40622
UR - https://arxiv.org/abs/2610.40622
AB - We investigate counting problems for discrete (geometric) structures in tropical settings, motivated by the comparison of the expressivity of linear programs and mean-payoff games. First, we give an upper bound on the number of coherent matching fields of type (n,r) and a lower bound on the number of combinatorial types of n-hyperplane sequences in the max-plus tropical space of dimension r−1. These structures are closely related, and our bounds establish that as n → ∞, for every fixed r their number equals n^(r−1)^2n+o(n). This in turn implies that the number of regular triangulations of the products of simplices Δ^n−1×Δ^r−1 is also n^(r−1)^2n+o(n), thereby answering a question of Santos. Second, we obtain that the number of labeled order types over the reals and over the signed tropical numbers coincide at first order, establishing a comparison of the expressivity of mean-payoff games and linear programs as measured by labeled order types. Last, the subclass of mean-payoff games known as parity games arise from linear programs by a ``double tropicalization.'' We show that the number of labeled order types obtained after this double tropicalization collapses.
ER -