Bounds on the number of cells and the dimension of the Dressian

Abstract

The {\em Dressian} of a matroid $M$ is the set of all valuations of $M$. This Dressian is the support of a polyhedral complex $\mathcal{D}r(M)$ whose open cells correspond 1-1 with matroid subdivisions of the matroid polytope of $M$. We present upper bounds on the number of cells and the dimension of $\mathcal{D}r(M)$. For matroids $M$ of rank $r\ge 3$ on $n$ elements we show that $$\ln \#\mathcal{D}r(M)\le \left(\genfrac{}{}{0ex}{}{n}{r}\right)O\left(\frac{\ln (n{)}^2}{n}\right)\text{ as }n\to \infty ,\text{and}\dim \mathcal{D}r(M)\le \left(\genfrac{}{}{0ex}{}{n}{r}\right)\frac{3}{n-r+3},$$ as well as some more detailed bounds that incorporate structural properties of such $M$. For uniform matroids $M=U(r,n)$, these upper bounds are comparable to lower bounds derived from valuations that are constructed from sparse paving matroids.