Finding the matroids with a specified set of non-bases

Question

I'm a grad student in algebraic geometry, and I've encountered a problem which requires me to produce an algorithm involving matroids. Since this isn't my area of expertise, I'm hoping someone knows an algorithm which is known to do this efficiently. The problem is as follows:

I'm dealing only with matroids of rank exactly $k$ on an $n$-element set. I have a bunch of $k$-element subsets of $\{1,\ldots,n\}$. Call a matroid "good" if all of these $k$-element sets are not bases. I want to find all the matroids $M$ which are minimal among the good ones, in the sense that there is no good matroid whose independent sets are a proper subset of those of $M$.

That's the whole problem; if you care about where it came from, keep reading. I'm looking at subvarieties of the Grassmannian $G(k,n)$ which are given by ideals generated by Plücker variables. The irreducible decomposition of such a subvariety can often (though I don't think always; I'm unclear on this point still) be found by taking the subsets in the above paragraph to be the ones that appear as subscripts of the Plücker variables that generate the ideal. Since primary decomposition in Macaulay2 is slow and checking ideal equality is fast, I'm hoping to handle a lot of cases of this procedure by trying to solve it combinatorially and checking to see if I got the right answer. I'd love to talk more about what I'm doing if anyone cares.

Answer 1

What is the number n of points in your matroid?

If n is at most 9, you can simply run by the ~400.000 matroids on at most 9 points. The sage matroid package will enumerate these matroids in half an hour. There is also a database of matroids that goes a bit further here: http://www-imai.is.s.u-tokyo.ac.jp/~ymatsu/matroid/index.html

I may not fully understand your original problem, but perhaps this is useful: given the 3-term grassmann-plucker relations and the fact that certain $k$-sets are dependent, many purely multiplicative relations follow. E.g. for $k=2$ and on a 4-set $\{a,b,c,d\}$, there is a g-p relation $[ab][cd]+[ad][bc]+[ac][db]=0$. If $ab$ is not a basis, then $[ab]=0$ and hence $[ad][bc]=-[ac][db]$. The multiplicative group generated by the nonzero brackets [..] and these relations is called the Tutte group in case of a matroid. This group is a lot easier to handle computationally that the ideal generated by the g-p relations. Perhaps creating this group will help you to make your guess for the right answer. If I understand your problem correctly, these multiplicative relations are contained in the ideal you are looking for.

Edit: the 3-way g-p relations can also be used in the converse direction: if $[ad][bc]=-[ac][db]$, then $[ab][cd]=0$ follows, i.e. either $[ab]=0$ or $[cd]=0$. But $[ab]=0$ means that $[ab]$ should be removed as a generator. Branching on these possibilities until $[ad][bc]\not=-[ac][db]$ everywhere may be better even than trying to find that matroid. The non-Pappos matroid may turn up when you just try to find a matroid, but this branching process will not terminate at the non-Pappos matroid.

Answer 2

There are a bit too many parameters - how big is k compared to n, how much is bunch and how fast you want the algorithm to be. In general, there cannot be a very fast algorithm, as there are too many such matroids (many depending on bunch), there could be as many as around $2^{n \choose k}$ such matroids. Unfortunately I only know these results in Hungarian, but nevertheless here is a link if you have someone around you who speaks Hungarian: 2.2.2 of http://www.cs.elte.hu/~frank/jegyzet/matroid/ulmat.2011.pdf