7
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Convexity is not matroidal property until you consider oriented matroid. And this still looks messy on first glance. $\endgroup$
    – Fedor Petrov
    Commented Apr 14, 2016 at 17:02
  • 1
    $\begingroup$ @FedorPetrov Right, but phrase it as "What is the minimal number of bases of a matroid of rank $d+1$ on $n$ points, where all circuits have size at least $4$?" (A circuit of size 1 would be the zero vector, so not a point of $\mathbb{P}^d$; a circuit of size 2 would be two parallel vectors, so the same point of $\mathbb{P}^d$ counted twice; a circuit of size 3 would give three colinear points in $\mathbb{P}^d$, so not the vertices of a polytope.) It is possible that the optimal answer to this question is not realizable as the vertices of a convex polytope, but I would bet otherwise. $\endgroup$
    – David E Speyer
    Commented Apr 14, 2016 at 17:34
  • $\begingroup$ @DavidSpeyer: what makes you think that this would be realizable? $\endgroup$
    – Moritz Firsching
    Commented Apr 14, 2016 at 17:53
  • $\begingroup$ @MoritzFirsching The nonbases of nonrealizable matroids tend to have little overlap with each other, so there can't be that many of them. Matroids with few bases tend to involve lots of points living in much lower dimensional flats, which is pretty easy to realize. All of the examples mentioned in mathoverflow.net/questions/212411/… , for example, are easily realizable. (Of course, this is all intuition until we actually prove something.) $\endgroup$
    – David E Speyer
    Commented Apr 14, 2016 at 17:57

1 Answer 1

Reset to default
4
$\begingroup$

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 circuit 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$.)

Proof. Use 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$ the induction hypothesis guarantees us 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}$.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Nice! And equality is always achievable by a convex polytope -- Take $n-k+p-1$ points in generic convex position in $\mathbb{P}^{p-1}$, and make the other $k-p+1$ vertices independent to span $\mathbb{P}^{k-1}$. $\endgroup$
    – David E Speyer
    Commented Apr 14, 2016 at 18:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .