Gammoid
From Egres Open
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
- ↑ Gy. Pap, Mader matroids are gammoids, EGRES Technical Report No. 2006-17.
- ↑ J.G. Oxley, A characterization of the ternary matroids with no M(K4)-minor, DOI link, author link
