How to prove whether a given matroid is a Gammoid?

Question

Statement : Given a matroid in some representation say $(E,I)$. How do we prove it is a gammoid?

For example to prove a matroid is transversal, we try to create a bipartite graph. If we are unable to(i.e. if we get some contradiction) then it is not transversal.

Similarly in cotransversal, we create a directed graph, and show all independent sets are linked to the fixed base using disjoint paths.

But if a matroid is a general gammoid, how can we prove it?

Answer according to me: One way I think is to show it is contraction of some transversal matroid(or restriction of cotransversal matroid). But how do we find that transversal(or cotransversal) matroid then?

score 2 · Accepted Answer · answered Oct 13 '15 at 16:00

2

According to Oxley, deciding whether a given matroid is a gammoid is still open. There is a way to check whether a given matroid is a strict gammoid, though, and you can find it in Oxley as well.

answered Oct 13 '15 at 16:00

immo

36

A fuller citation of this work by Oxley (Matroid Theory, 2006?) would improve your answer, as would a brief summary of the method for checking for a strict gammoid. – hardmath Oct 13 '15 at 16:26

How to prove whether a given matroid is a Gammoid?

1 Answers1