View source for Gammoid

{{Short description|Abstraction of disjoint paths in directed graphs}}
In [[matroid theory]], a field within mathematics, a '''gammoid''' is a certain kind of matroid, describing sets of [[Vertices (graph theory)|vertices]] that can be reached by vertex-disjoint [[Path (graph theory)|paths]] in a [[directed graph]].

The concept of a gammoid was introduced and shown to be a matroid by {{harvs|first=Hazel|last=Perfect|authorlink=Hazel Perfect|year=1968|txt}}, based on considerations related to [[Menger's theorem]] characterizing the obstacles to the existence of systems of disjoint paths.<ref>{{citation
 | last = Perfect | first = Hazel
 | doi = 10.1016/0022-247X(68)90163-7
 | journal = Journal of Mathematical Analysis and Applications
 | mr = 0224494
 | pages = 96–111
 | title = Applications of Menger's graph theorem
 | volume = 22
 | year = 1968| doi-access = free
 }}.</ref> Gammoids were given their name by {{harvtxt|Pym|1969}}<ref name="pym69">
{{citation
 | last = Pym | first = J. S.
 | doi = 10.1112/jlms/s1-44.1.542
 | issue = 1
 | journal = Journal of the London Mathematical Society
 | pages = 542–550
 | title = The Linking of Sets in Graphs
 | volume = s1-44
 | year = 1969}}.</ref> and studied in more detail by {{harvtxt|Mason|1972}}.<ref name="mason72">{{citation
 | last = Mason | first = J. H.
 | doi = 10.1112/plms/s3-25.1.55
 | issue = 1
 | journal = Proceedings of the London Mathematical Society
 | mr = 0311496
 | pages = 55–74
 | series = Third Series
 | title = On a class of matroids arising from paths in graphs
 | volume = 25
 | year = 1972}}.</ref>

==Definition==
Let <math>G</math> be a directed graph, <math>S</math> be a set of starting vertices, and <math>T</math> be a set of destination vertices (not necessarily disjoint from <math>S</math>). The gammoid <math>\Gamma</math> derived from this data has <math>T</math> as its set of elements. A subset <math>I</math> of <math>T</math> is independent in <math>\Gamma</math> if there exists a set of vertex-disjoint paths whose starting points all belong to <math>S</math> and whose ending points are exactly <math>I</math>.<ref name="schrijver">{{citation
 | last = Schrijver | first = Alexander | author-link = Alexander Schrijver
 | isbn = 3-540-44389-4
 | location = Berlin
 | mr = 1956925
 | pages = 659–661
 | publisher = Springer-Verlag
 | series = Algorithms and Combinatorics
 | title = Combinatorial Optimization: Polyhedra and Efficiency. Vol. B: Matroids, Trees, Stable Sets
 | url = https://books.google.com/books?id=mqGeSQ6dJycC&pg=PA659
 | volume = 24
 | year = 2003}}.</ref>

A '''strict gammoid''' is a gammoid in which the set <math>T</math> of destination vertices consists of every vertex in <math>G</math>. Thus, a gammoid is a restriction of a strict gammoid, to a subset of its elements.<ref name="schrijver"/><ref name=Ox100>{{harvnb|Oxley|2006|p=100}}</ref>

==Example==
Consider the [[uniform matroid]] <math>U{}^r_n</math> on a set of <math>n</math> elements, in which every set of <math>r</math> or fewer elements is independent. One way to represent this matroid as a gammoid would be to form a [[complete bipartite graph]] <math>K_{r,n}</math> with a set <math>S</math> of <math>r</math> vertices on one side of the bipartition, with a set <math>T</math> of <math>n</math> vertices on the other side of the bipartition, and with every edge directed from <math>S</math> to <math>T.</math> In this graph, a subset of <math>T</math> is the set of endpoints of a set of disjoint paths if and only if it has <math>r</math> or fewer vertices, for otherwise there aren't enough vertices in <math>S</math> to start the paths. The special structure of this graph shows that the uniform matroid is a [[transversal matroid]] as well as being a gammoid.<ref>{{citation
 | last = Oxley | first = James G. | authorlink = James Oxley
 | isbn = 9780199202508
 | pages = 48–49
 | publisher = Oxford University Press
 | series = Oxford Graduate Texts in Mathematics
 | title = Matroid Theory
 | volume = 3
 | year = 2006}}.</ref>

Alternatively, the same uniform matroid <math>U{}^r_n</math> may be represented as a gammoid on a smaller graph, with only <math>n</math> vertices, by choosing a subset <math>S</math> of <math>r</math> vertices and connecting each of the chosen vertices to every other vertex in the graph. Again, a subset of the vertices of the graph can be endpoints of disjoint paths if and only if it has <math>r</math> or fewer vertices, because otherwise there are not enough vertices that can be starts of paths. In this graph, every vertex corresponds to an element of the matroid, showing that the uniform matroid is a strict gammoid.<ref>{{harvtxt|Oxley|2006}}, p. 100.</ref>

==Menger's theorem and gammoid rank==
The rank of a set <math>X\subset T</math> in a gammoid defined from a graph <math>G</math> and vertex subsets <math>S</math> and <math>T</math> is, by definition, the maximum number of vertex-disjoint paths from <math>S</math> to <math>X</math>. By [[Menger's theorem]], it also equals the minimum cardinality of a set <math>Y</math> that intersects every path from <math>S</math> to <math>X</math>.<ref name="schrijver"/>

==Relation to transversal matroids==
A [[transversal matroid]] is defined from a [[family of sets]]: its elements are the elements of the sets, and a set <math>X</math> of these elements is independent whenever there exists a one-to-one matching of the elements of <math>X</math> to disjoint sets containing them, called a [[system of distinct representatives]]. Equivalently, a transversal matroid may be represented by a special kind of gammoid, defined from a directed [[bipartite graph]] <math>(S,T,E)</math> that has a vertex in <math>S</math> for each set, a vertex in <math>T</math> for each element, and an edge from each set to each element contained in it.

Less trivially, the strict gammoids are exactly the [[dual matroid]]s of the transversal matroids. To see that every strict gammoid is dual to a transversal matroid, let <math>\gamma</math> be a strict gammoid defined from a directed graph <math>G</math> and starting vertex set <math>S</math>, and consider the transversal matroid for the family of sets <math>N_v</math> for each vertex <math>v\in V(G)\setminus S</math>, where vertex <math>u</math> belongs to <math>N_v</math> if it equals <math>v</math> or it has an edge to <math>v</math>. Any basis of the strict gammoid, consisting of the endpoints of some set of <math>|S|</math> disjoint paths from <math>S</math>, is the complement of a basis of the transversal matroid, matching each <math>N_v</math> to the vertex <math>u</math> such that <math>uv</math> is a path edge (or <math>v</math> itself, if <math>v</math> does not participate in one of the paths). Conversely every basis of the transversal matroid, consisting of a representative <math>u_v</math> for each <math>N_v</math>, gives rise to a complementary basis of the strict gammoid, consisting of the endpoints of the paths formed by the set of edges <math>u_vv</math>. This result is due to [[Aubrey Ingleton|Ingleton]] and [[Mike Piff|Piff]].<ref name="schrijver"/><ref name="pi">{{citation
 | last1 = Ingleton | first1 = A. W.
 | last2 = Piff | first2 = M. J.
 | doi = 10.1016/0095-8956(73)90031-2
 | journal = Journal of Combinatorial Theory
 | mr = 0329936
 | pages = 51–68
 | series = Series B
 | title = Gammoids and transversal matroids
 | volume = 15
 | year = 1973| doi-access = free
 }}.</ref>

To see, conversely, that every transversal matroid is dual to a strict gammoid, find a subfamily of the sets defining the matroid such that the subfamily has a system of distinct representatives and defines the same matroid. Form a graph that has the union of the sets as its vertices and that has an edge to the representative element of each set from the other members of the same set. Then the sets <math>N_v</math> formed as above for each representative element <math>v</math> are exactly the sets defining the original transversal matroid, so the strict gammoid formed by this graph and by the set of representative elements is dual to the given transversal matroid.<ref name="schrijver"/><ref name="pi"/>

As an easy consequence of the Ingleton-Piff Theorem, every gammoid is a [[matroid minor|contraction]] of a transversal matroid. The gammoids are the smallest class of matroids that includes the transversal matroids and is closed under duality and taking [[matroid minor|minor]]s.<ref name="schrijver"/><ref name=Ox115>{{harvnb|Oxley|2006|p=115}}</ref><ref>{{citation
 | last = Welsh | first = D. J. A. | authorlink = Dominic Welsh
 | isbn = 9780486474397
 | pages = 222–223
 | publisher = Courier Dover Publications
 | title = Matroid Theory
 | url = https://books.google.com/books?id=QL2iYMBLpFwC&pg=PA222
 | year = 2010}}.</ref>

==Representability==
It is not true that every gammoid is [[regular matroid|regular]], i.e., [[Matroid representation|representable]] over every field. In particular, the uniform matroid <math>U{}^2_4</math> is not a binary matroid, and more generally the <math>n</math>-point line <math>U{}^2_n</math> can only be represented over fields with <math>n-1</math> or more elements. However, every gammoid may be represented over almost every [[finite field]].<ref name="mason72"/><ref name="schrijver"/> More specifically, a gammoid with element set <math>S</math> may be represented over every [[field (mathematics)|field]] that has at least <math>2^{|S|}</math> elements.<ref name="schrijver"/><ref>{{citation
 | last = Atkin | first = A. O. L.
 | doi = 10.1016/0095-8956(72)90053-6
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 0316281
 | pages = 179–182
 | series = Series B
 | title = Remark on a paper of Piff and Welsh
 | volume = 13
 | year = 1972| issue = 2
 | doi-access = free
 }}.</ref><ref>{{citation
 | last = Lindström | first = Bernt
 | doi = 10.1112/blms/5.1.85
 | journal = The Bulletin of the London Mathematical Society
 | mr = 0335313
 | pages = 85–90
 | title = On the vector representations of induced matroids
 | volume = 5
 | year = 1973}}.</ref>

==References==
{{reflist}}

[[Category:Matroid theory]]
[[Category:Graph connectivity]]