2011/09/21 by David Haws, David C. Haws, Haws, David C.
Computer Science · Mathematics · #05 #52B #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #math.CO #msc:05 #msc:52B
paper · pdf · doi:10.48550/arxiv.1109.4453
10 pages, 5 figures
arxiv created 2011/09/21 · openalex publication_date 2011/09/21 · arxiv updated 2011/09/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
De Loera et al. 2009, showed that when the rank is fixed the Ehrhart polynomial of a matroid polytope can be computed in polynomial time when the number of elements varies. A key to proving this is the fact that the number of simplicial cones in any triangulation of a tangent cone is bounded polynomially in the number of elements when the rank is fixed. The authors speculated whether or not the Ehrhart polynomial could be computed in polynomial time in terms of the number of bases, where the number of elements and rank are allowed to vary. We show here that for the uniform matroid of rank r on n elements, the number of simplicial cones in any triangulation of a tangent cone is n-2 \choose r-1. Therefore, if the rank is allowed to vary, the number of simplicial cones grows exponentially in n. Thus, it is unlikely that a Brion-Lawrence type of approach, such as Barvinok's Algorithm, can compute the Ehrhart polynomial efficiently when the rank varies with the number of elements. To prove this result, we provide a triangulation in which the maximal simplicies are in bijection with the spanning thrackles of the complete bipartite graph Kr,n-r.