6
$\begingroup$

I'm interested in connected matroids $M$ on the ground set $[n]$ for which there is no connected matroid on $[n]$ of the same rank but with a strictly smaller set of bases (by inclusion). Equivalently, the matroid polytope of $M$ has dimension $n-1$ and does not contain any other matroid polytope of dimension $n-1$. Obvious examples are uniform matroids of ranks $1$ and $n-1$. A less trivial example for $n=4$ is a matroid of rank 2 with 5 bases.

What is known about such matroids? Is there some classification or interesting alternative characterization?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

In general there does not seem to be a nice classification. You're asking for connected matroids of a given rank which are minimal in the "weak map order" (a weak map between matroids of the same rank is an inclusion of bases). In Weak maps of combinatorial geometries, Theorem 6.10, Dean Lucas shows that every connected binary matroid is minimal. In particular, every connected graphic matroid is minimal. I believe there are examples which are not binary.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Nice! The specific matroids I suspected of being minimal are indeed binary. In fact, a few days ago I found the paper arxiv.org/abs/1809.08965 where it is shown that binary matroids have the (seemingly) weaker property of being indecomposable. There in Proposition 32 a certain non-binary matroid is shown to also be indecomposable but the proof actually implies its minimality. This is to comment on the last sentence in your answer. $\endgroup$
    – Igor Makhlin
    Commented Aug 20, 2023 at 22:04
  • $\begingroup$ P.S. It isn't hard to see that indecomposability is equivalent to minimality via the so-called corank subdivision. $\endgroup$
    – Igor Makhlin
    Commented Aug 23, 2023 at 12:36
  • $\begingroup$ I'm not entirely sure what you mean by "corank subdivision," but in general the regular subdivision induced by lifting to height equal to the corank of another matroid does not in general give a subdivision into matroid polytopes (although this is true for the uniform matroid). See Theorem 5.2 in arxiv.org/pdf/1902.05592.pdf. $\endgroup$
    – Matt Larson
    Commented Aug 23, 2023 at 14:56
  • $\begingroup$ I believe the question of whether indecomposable matroids are minimal is open. Most the experts I've talked to believe that they need not be, but an example will be hard to find. $\endgroup$
    – Matt Larson
    Commented Aug 23, 2023 at 15:00
  • $\begingroup$ Yes, that's what I meant by "corank subdivision" and you're absolutely right, I don't know why I assumed that this subdivision is matroidal. $\endgroup$
    – Igor Makhlin
    Commented Aug 23, 2023 at 22:09
7
$\begingroup$

I think you want Theorem 2.1 On the Ehrhart Polynomial of Minimal Matroids by Ferroni. Note Theorem 2.1 cites previous work that may be of interest, but I know of these matroids from this recent paper.

Theorem 2.1 says if you have a connected matroid on $n$ elements of rank $k$ then the number of bases is at least $k(n-k)+1$. Furthermore, there is a unique matroid up to isomorphism that realizes this bound (and that matroid turns out to be graphic). The construction of this matroid is described in Section 2 of the linked paper.

Edit: It has been clarified that the question wishes to address minimality by inclusion of the set of bases. The answer above completely deals with the minimal by cardinality case (which is the subcase of the whole question). In Remark 2.9 of the paper linked an example of a minimal by inclusion matroid which is not minimal by cardinality is given. So, there are indeed other matroids OP is curious about.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Thanks, this is indeed related to my question but they seem to show that their basis set is minimal by size rather than by inclusion. (I added the words "by inclusion" for clarity.) $\endgroup$
    – Igor Makhlin
    Commented Aug 12, 2023 at 20:40
  • 3
    $\begingroup$ Yes, this is the cardinality case. I edited my answer to make it apparent there are other matroids you are still interested in. And perhaps you already saw the paper I linked gives one example of such a matroid. $\endgroup$
    – John Machacek
    Commented Aug 13, 2023 at 17:02
  • 1
    $\begingroup$ Cool, no I did not see Remark 2.9, thanks for pointing it out. This matroid, as well as their minimal matroids, appears in the family I'm dealing with. $\endgroup$
    – Igor Makhlin
    Commented Aug 14, 2023 at 0:04

You must log in to answer this question.

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