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).
be a set of destination vertices (not necessarily disjoint from
if there exists a set of vertex-disjoint paths whose starting points all belong to
of destination vertices consists of every vertex in
One way to represent this matroid as a gammoid would be to form a complete bipartite graph
vertices on one side of the bipartition, with a set
vertices on the other side of the bipartition, and with every edge directed from
Again, a subset of the vertices of the graph can be endpoints of disjoint paths if and only if it has
In this graph, every vertex corresponds to an element of the matroid, showing that the uniform matroid is a strict gammoid.
is, by definition, the maximum number of vertex-disjoint paths from
By Menger's theorem, it also equals the minimum cardinality of a set
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
To see that every strict gammoid is dual to a transversal matroid, let
be a strict gammoid defined from a directed graph
, and consider the transversal matroid for the family of sets
Any basis of the strict gammoid, consisting of the endpoints of some set of
, is the complement of a basis of the transversal matroid, matching each
Conversely every basis of the transversal matroid, consisting of a representative
, 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.
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] It is not true that every gammoid is regular, i.e., representable over every field.
However, every gammoid may be represented over almost every finite field.
[3][4] More specifically, a gammoid with element set