2024 Workshop on (Mostly) Matroids

Bounds on the number of cells of the Dressian

22 Aug 2024, 14:40

25m

S236 (IBS Science Culture Center)

Presentation (25 min)

Speaker

Rudi Pendavingh (Eindhoven Technical University)

Description

A valuation of a matroid $M$ with set of bases $\mathcal{B}$ is a function $\nu :\mathcal{B}\to \mathbb{R}$ so that

• (V) for all $B,B^{\prime }\in \mathcal{B}$ and all $e\in B\setminus B^{\prime }$ there exists an $f\in B^{\prime }\setminus B$ such that
  $\nu (B)+\nu (B^{\prime })\ge \nu (B-e+f)+\nu (B^{\prime }+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 $\mathrm{\#}\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\ge t\ge 3$ , then

$\frac{\dim \mathcal{D}(M)}{(\genfrac{}{}{0ex}{}{n}{r})}\le \frac{max\{\dim \mathcal{D}(M/S),S\in (\genfrac{}{}{0ex}{}{E}{r-t})\text{ independent}\}}{(\genfrac{}{}{0ex}{}{n-r+t}{t})}\le \frac{3}{n-r+3}$

and

$\frac{{\log }_2\mathrm{\#}\mathcal{D}(M)}{(\genfrac{}{}{0ex}{}{n}{r})}\le \frac{max\{{\log }_2\mathrm{\#}\mathcal{D}(M/S):S\in (\genfrac{}{}{0ex}{}{E}{r-t})\text{ independent }\}}{(\genfrac{}{}{0ex}{}{n-r+t}{t})}O(\ln (n))\le \frac{O(\ln (n{)}^2)}{n}.$

For uniform matroids $M=U(r,n)$ these upper bounds may be compared to the lower bounds

$\frac{1}{n}\le \frac{\dim \mathcal{D}(M)}{(\genfrac{}{}{0ex}{}{n}{r})},\frac{1}{n}\le \frac{{\log }_2\mathrm{\#}\mathcal{D}(M)}{(\genfrac{}{}{0ex}{}{n}{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.