pipette
ESEspañol

The Number of Tropical Order Types and Coherent Matching Fields

Xavier Allamigeon, Yiyuan Chen, St\'ephane Gaubert, Xavier Goaoc

Preprint

In the authors' words

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 and a lower bound on the number of combinatorial types of -hyperplane sequences in the max-plus tropical space of dimension . These structures are closely related, and our bounds establish that as , for every fixed their number equals . This in turn implies that the number of regular triangulations of the products of simplices is also , 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.

Main resultThe abstract does not state a limitation.

Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 35 pages, 16 figures