Q:

minimum number of bases of a matroid, that comes from a convex polytope

Given a d-dimensional polytope P with n points, then what is the minimum number of simplices that are spanned by vertices of P? This question led my research to matroids and so my question is: what is the minimum number of bases af a matroid, that comes from a fulldimensional convex set with n vertices in dimension d? Here you have to think of affine independence or linear independence in the projective plane in dimension d+.
The upper bound is obviously $n \choose d+1$, but the lower bound seems to be quite hard.
My theory is, that it should be bounded by $n-d+2 \choose 3$. This refers to a (n-d+2)-gon in a 2-dimensional subspace and the other vertices spanning the other d-2 dimensions. But until now i couldn't find a proof. As I do not know a lot about matroids i hope that in terms of matroids this turns out to be easier, than in terms of polytopes.

A:

It looks that David Speyer strengthening holds. Namely, if a matroid $M$ on a set $E$, $|E|=n$, has rank $k\leqslant n$ and minimal crcuit size at least $p$, $k\geqslant p-1$, than $M$ has at least $\binom{n-k+p-1}{p-1}$ bases. (In our situation $k=d+1$, $p=4$.) Prove by induction. Cases $n=k$ and $k=p-1$ are clear. So assume that $n>k>(p-1)$ and the claim holds for less $n$.
If there exists a bridge $a\in E$, we simply remove it, $n-k$ does not change. If there are no bridges, then for any $a\in E$ induction proposition gets as at least $\binom{n-k+p-2}{p-1}$ bases without $a$, this have to be multiplied by $n$ (choices of $a$) and divided by $n-k$ (number of times we counted each base). We get even more than we need: $\frac{n}{n-k}\binom{n-k+p-2}{p-1}\geqslant \binom{n-k+p-1}{p-1}$.

