Speaker
Description
A valuation of a matroid $M$ with set of bases $\mathcal{B}$ is a function $\nu:\mathcal{B}\rightarrow\mathbb{R}$ so that
- (V) for all $B, B'\in \mathcal{B}$ and all $e\in B\setminus B'$ there exists an $f\in B'\setminus B$ such that
$ \nu(B)+\nu(B')\geq \nu(B-e+f)+\nu(B'+e-f).$
The Dressian $\mathcal{D}(M)$ is defined as the set of all valuations of $M$. The Dressian of $M$ is the support of a polyhedral complex in $\mathbb{R}^{\mathcal{B}}$ whose cells are polyhedral cones. We investigate $\#\mathcal{D}(M)$, the number of cells, and $\dim \mathcal{D}(M)$, the maximum dimension of any cell.
We show that if $M$ is a matroid on an $n$-element groundset of rank $r\geq t\geq 3$ , then
$\qquad\qquad\qquad\qquad\frac{\dim \mathcal{D}(M)}{{n\choose r}}\leq \frac{\max\{\dim\mathcal{D}(M/S), ~S\in {E\choose r-t}\text{ independent}\}}{{n-r+t\choose t}}\leq \frac{3}{n-r+3}$
and
$\qquad\qquad\qquad\frac{\log_2 \#\mathcal{D}(M)}{{n\choose r}}\leq \frac{\max\{\log_2 \#\mathcal{D}(M/S): ~S\in {E\choose r-t}\text{ independent }\}}{{n-r+t\choose t}}O(\ln(n))\leq \frac{O\left(\ln(n)^2\right)}{n}.$
For uniform matroids $M=U(r,n)$ these upper bounds may be compared to the lower bounds
$\qquad\qquad\qquad\qquad\qquad\qquad\frac{1}{n}\leq \frac{\dim \mathcal{D}(M)}{{n\choose r}},\qquad \frac{1}{n}\leq \frac{\log_2 \#\mathcal{D}(M)}{{n\choose r}}$
that follow a previously known construction of valuations of $U(r,n)$ from matroids of rank $r$ on $n$ elements. For non-uniform matroids, we also obtain somewhat tighter upper bounds in terms of the number of free generators of the Tutte group of $M$.
Our methods include an analogue of Shearers' Entropy Lemma for bounding the dimension of a linear subspace, and a container method for collections of linear subspaces.
