Gammoid

From Egres Open
Jump to: navigation, search

A gammoid is a matroid that can be obtained using a directed graph D=(V,A) and node sets [math]S,T \subseteq V[/math] the following way. A node set X is linked to a node set Y if [math]|X|=|Y|[/math] and there are [math]|X|[/math] completely node-disjoint directed paths from X to Y. The ground set of the gammoid is S, and the independent sets are the subsets of S that are linked to some subset of T.

Properties and examples

  • A transversal matroid is a gammoid defined by a bipartite graph G=(S,T;E), oriented from S to T
  • Gammoids are exactly the contractions of transversal matroids
  • Gammoids are exactly the minors of deltoids
  • Gammoids are strongly base orderable
  • Matching matroids are gammoids (since they are transversal matroids)
  • Mader matroids are gammoids (see Pap [1])
  • An excluded minor characterization of ternary gammoids is given in [2]

References

  1. Gy. Pap, Mader matroids are gammoids, EGRES Technical Report No. 2006-17.
  2. J.G. Oxley, A characterization of the ternary matroids with no M(K4)-minor, DOI link, author link