Checking whether a set family forms a matroid.

Question

Given a set family, what is the best way (empirically) to check whether the set family is equivalent to set of independent sets of some matroid. The input can be either the set family explicitly or bunch of cardinality constraints that must be satisfied. For example, given a universe E, subsets $A_1,..,A_k$ of E and positive integers $b_1,...,b_k$, a set F is in the family iff $|F\cap A_i|<= b_i$ for each $1<= i<= k$. Check whether the family is a matroid.

Answer 1

One way is to delete an element $x$ from your alleged matroid $M$, recursively check that the smaller structure $M'$ is a matroid, and then check that adding back $x$ gives you a single-element extension of $M'$. An algorithm for testing for single-element extensions is explained in this paper by Mayhew and Royle, in which they compute all matroids with up to nine elements.

Answer 2

You could use the definition. For your example, if $A_i$s are disjoints, the answer is yes. It is a partition matroid. Otherwise, the answer is no in general.

Answer 3

Here's a probabilistic approach.

First check if your set family $\mathcal{I}$ is closed under taking subsets. If not, then it is not a matroid. Next assign a 'random' weight function $w: S \to \mathbb{R}_{+}$, to the ground set $S$. Now run the greedy algorithm. If $\mathcal{I}$ is indeed a matroid, then the greedy algorithm will output a member $I$ of $\mathcal{I}$ of maximum weight. However, we can directly compute the weight of each maximal (under inclusion) member of $\mathcal{I}$. So, if $I$ does not have maximum weight, then $\mathcal{I}$ is not a matroid. If $I$ does have maximum weight, then this does not mean that $\mathcal{I}$ is a matroid, we may have just gotten lucky. So, we choose another random weight function and repeat. I haven't analyzed how many times we need to do this to be reasonably 'sure' that $\mathcal{I}$ is a matroid.