# Checking whether a set family forms a matroid.

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.

-
Matroid: en.wikipedia.org/wiki/Matroid – Joel David Hamkins Jun 4 '10 at 20:58

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.

-
Thanks Timothy. This certainly looks a much better way than doing an exhaustive search. – Mohit Singh Jun 6 '10 at 22:43

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.

-

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.

-
Thanks for the approach. I thought about it but since the families in question are very close to matroids and exchange axioms are violated on few places, I am not sure checking a few cases will work. But it certainly will work as a quick dirty check. – Mohit Singh Jun 6 '10 at 22:45