Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Matroid: en.wikipedia.org/wiki/Matroid –  Joel David Hamkins Jun 4 '10 at 20:58

3 Answers 3

up vote 4 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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