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

Given two matroids $M$ and $M'$ over the same universe $E$, and some element $x \in E$, I am interested in the importance of $x$ for the intersection (the common independent sets) of $M$ and $M'$.

It is easy to test whether $x$ is contained in all maximum-cardinality common independent sets: for this we can simply compute the size $n$ of a maximum set in $M \cap M'$ by a matroid intersection algorithm, compute the size $n'$ of a maximum set in $(M - x) \cap (M' - x)$, and test whether these have the same size. Element $x$ is in all maximum-cardinality common independent sets of $M$ and $M'$ iff $n = n'+1$.

But now consider the inclusion-wise maximal sets in $M \cap M'$, which may be smaller than a maximum common independent set. I want to determine algorithmically whether $x$ is contained in all such inclusion-wise maximal common independent sets. Clearly, a necessary condition is that $x$ is in all maximum common independent sets; but this is not sufficient. Is there a polynomial-time algorithm to determine whether $x$ is in all maximal common independent sets of two represented matroids?

I am even interested in the case that both $M$ and $M'$ are transversal matroids. Has this topic been studied before? My literature search did not turn up anything useful.

Edit: I just realized that the following question is equivalent to the one I described above: given two matroids $M$ and $M'$ and an element $x$, does one of the two matroids contain a circuit $C \supseteq {x}$ such that $C - x$ is independent in the other matroid? I'm hoping that this alternative formulation might ring a bell for someone.

share|improve this question
    
How are your matroids represented? If you have them represented as a set of circuits, then there's a clear algorithm that will check your condition in time $m^2$ (where $m$ is the total number of circuits). But I believe passing from the maximal independent set representation to the circuit representation to be NP-hard... –  Russ Woodroofe May 17 '13 at 19:48
    
Indeed, if there is a list of circuits then the alternative formulation is easy to verify. I'm interested in the setting where $M$ and $M'$ are given by independence oracles, and (even) in the setting where $M$ and $M'$ are transversal matroids represented by 2 set systems whose partial transversals are the independent sets of the matroids. –  Bart Jansen May 22 '13 at 11:33
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.