In matroid theory, a field within mathematics, a gammoid is a certain kind of matroid, describing sets of vertices that can be reached by vertex-disjoint paths in a directed graph.

The concept of a gammoid was introduced and shown to be a matroid by Hazel Perfect (1968), based on considerations related to Menger's theorem characterizing the obstacles to the existence of systems of disjoint paths.[1] Gammoids were given their name by Pym (1969)[2] and studied in more detail by Mason (1972).[3]

Definition

edit

Let   be a directed graph,   be a set of starting vertices, and   be a set of destination vertices (not necessarily disjoint from  ). The gammoid   derived from this data has   as its set of elements. A subset   of   is independent in   if there exists a set of vertex-disjoint paths whose starting points all belong to   and whose ending points are exactly  .[4]

A strict gammoid is a gammoid in which the set   of destination vertices consists of every vertex in  . Thus, a gammoid is a restriction of a strict gammoid, to a subset of its elements.[4][5]

Example

edit

Consider the uniform matroid   on a set of   elements, in which every set of   or fewer elements is independent. One way to represent this matroid as a gammoid would be to form a complete bipartite graph   with a set   of   vertices on one side of the bipartition, with a set   of   vertices on the other side of the bipartition, and with every edge directed from   to   In this graph, a subset of   is the set of endpoints of a set of disjoint paths if and only if it has   or fewer vertices, for otherwise there aren't enough vertices in   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.[6]

Alternatively, the same uniform matroid   may be represented as a gammoid on a smaller graph, with only   vertices, by choosing a subset   of   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   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.[7]

Menger's theorem and gammoid rank

edit

The rank of a set   in a gammoid defined from a graph   and vertex subsets   and   is, by definition, the maximum number of vertex-disjoint paths from   to  . By Menger's theorem, it also equals the minimum cardinality of a set   that intersects every path from   to  .[4]

Relation to transversal matroids

edit

A transversal matroid is defined from a family of sets: its elements are the elements of the sets, and a set   of these elements is independent whenever there exists a one-to-one matching of the elements of   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   that has a vertex in   for each set, a vertex in   for each element, and an edge from each set to each element contained in it.

Less trivially, the strict gammoids are exactly the dual matroids of the transversal matroids. To see that every strict gammoid is dual to a transversal matroid, let   be a strict gammoid defined from a directed graph   and starting vertex set  , and consider the transversal matroid for the family of sets   for each vertex  , where vertex   belongs to   if it equals   or it has an edge to  . Any basis of the strict gammoid, consisting of the endpoints of some set of   disjoint paths from  , is the complement of a basis of the transversal matroid, matching each   to the vertex   such that   is a path edge (or   itself, if   does not participate in one of the paths). Conversely every basis of the transversal matroid, consisting of a representative   for each  , gives rise to a complementary basis of the strict gammoid, consisting of the endpoints of the paths formed by the set of edges  . This result is due to Ingleton and Piff.[4][8]

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   formed as above for each representative element   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.[4][8]

As an easy consequence of the Ingleton-Piff Theorem, every gammoid is a 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 minors.[4][9][10]

Representability

edit

It is not true that every gammoid is regular, i.e., representable over every field. In particular, the uniform matroid   is not a binary matroid, and more generally the  -point line   can only be represented over fields with   or more elements. However, every gammoid may be represented over almost every finite field.[3][4] More specifically, a gammoid with element set   may be represented over every field that has at least   elements.[4][11][12]

References

edit
  1. ^ Perfect, Hazel (1968), "Applications of Menger's graph theorem", Journal of Mathematical Analysis and Applications, 22: 96–111, doi:10.1016/0022-247X(68)90163-7, MR 0224494.
  2. ^ Pym, J. S. (1969), "The Linking of Sets in Graphs", Journal of the London Mathematical Society, s1-44 (1): 542–550, doi:10.1112/jlms/s1-44.1.542.
  3. ^ a b Mason, J. H. (1972), "On a class of matroids arising from paths in graphs", Proceedings of the London Mathematical Society, Third Series, 25 (1): 55–74, doi:10.1112/plms/s3-25.1.55, MR 0311496.
  4. ^ a b c d e f g h Schrijver, Alexander (2003), Combinatorial Optimization: Polyhedra and Efficiency. Vol. B: Matroids, Trees, Stable Sets, Algorithms and Combinatorics, vol. 24, Berlin: Springer-Verlag, pp. 659–661, ISBN 3-540-44389-4, MR 1956925.
  5. ^ Oxley 2006, p. 100
  6. ^ Oxley, James G. (2006), Matroid Theory, Oxford Graduate Texts in Mathematics, vol. 3, Oxford University Press, pp. 48–49, ISBN 9780199202508.
  7. ^ Oxley (2006), p. 100.
  8. ^ a b Ingleton, A. W.; Piff, M. J. (1973), "Gammoids and transversal matroids", Journal of Combinatorial Theory, Series B, 15: 51–68, doi:10.1016/0095-8956(73)90031-2, MR 0329936.
  9. ^ Oxley 2006, p. 115
  10. ^ Welsh, D. J. A. (2010), Matroid Theory, Courier Dover Publications, pp. 222–223, ISBN 9780486474397.
  11. ^ Atkin, A. O. L. (1972), "Remark on a paper of Piff and Welsh", Journal of Combinatorial Theory, Series B, 13 (2): 179–182, doi:10.1016/0095-8956(72)90053-6, MR 0316281.
  12. ^ Lindström, Bernt (1973), "On the vector representations of induced matroids", The Bulletin of the London Mathematical Society, 5: 85–90, doi:10.1112/blms/5.1.85, MR 0335313.