Volumes and Tangent Cones of Matroid Polytopes

Details Volumes and Tangent Cones of Matroid Polytopes Volumes and Tangent Cones of Matroid Polytopes

2011-09-21

arxiv.org/abs/1109.4453v1

Mathematics

Combinatorics

10 pages, 5 figures

Scientific paper

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 $K_{r,n-r}$.

Affiliated with

Also associated with

No associations

Rating

Volumes and Tangent Cones of Matroid Polytopes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Volumes and Tangent Cones of Matroid Polytopes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Volumes and Tangent Cones of Matroid Polytopes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-256906