6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ There is a lot of good work (not by me) going into a Sage matroid package. As I understand it, it is not yet part of the Sage package, but you can get a beta version from Stefan van Zwam to play around with. There may be a method that does precisely what you need. $\endgroup$
    – Tony Huynh
    Sep 15, 2012 at 11:21

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Welcome to MO Rudi! I should have mentioned that Rudi is one of the people doing the good work on the Sage matroid package that I alluded to in the comments. $\endgroup$
    – Tony Huynh
    Nov 10, 2012 at 0:42
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ This is sad, but about what I expected. I implemented a "dumb" version of the algorithm, and it's been running for hours in a case where k is 3 and n is 8, but I was hoping there's something better. Even if it can't be too fast, do you have a recommendation for how I might want to go about implementing it? $\endgroup$ Sep 15, 2012 at 23:39
  • $\begingroup$ Sorry, no clue. But again, just the size of your output might be 2^{50} or so, which really isn't something you can deal with. $\endgroup$
    – domotorp
    Sep 16, 2012 at 7:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.