Gammoid

A transversal matroid is defined from a family of sets: its elements are the elements of the sets, and a set ${\displaystyle X}$ of these elements is independent whenever there exists a one-to-one matching of the elements of ${\displaystyle X}$ 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 ${\displaystyle (S,T,E)}$ that has a vertex in ${\displaystyle S}$ for each set, a vertex in ${\displaystyle T}$ 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 ${\displaystyle \gamma }$ be a strict gammoid defined from a directed graph ${\displaystyle G}$ and starting vertex set ${\displaystyle S}$, and consider the transversal matroid for the family of sets ${\displaystyle N_{v}}$ for each vertex ${\displaystyle v\in V(G)\setminus S}$, where vertex ${\displaystyle u}$ belongs to ${\displaystyle N_{v}}$ if it equals ${\displaystyle v}$ or it has an edge to ${\displaystyle v}$. Any basis of the strict gammoid, consisting of the endpoints of some set of ${\displaystyle |S|}$ disjoint paths from ${\displaystyle S}$, is the complement of a basis of the transversal matroid, matching each ${\displaystyle N_{v}}$ to the vertex ${\displaystyle u}$ such that ${\displaystyle uv}$ is a path edge (or ${\displaystyle v}$ itself, if ${\displaystyle v}$ does not participate in one of the paths). Conversely every basis of the transversal matroid, consisting of a representative ${\displaystyle u_{v}}$ for each ${\displaystyle N_{v}}$, gives rise to a complementary basis of the strict gammoid, consisting of the endpoints of the paths formed by the set of edges ${\displaystyle u_{v}v}$. 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 ${\displaystyle N_{v}}$ formed as above for each representative element ${\displaystyle v}$ 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. In particular, the uniform matroid ${\displaystyle U{}_{4}^{2}}$ is not a binary matroid, and more generally the ${\displaystyle n}$-point line ${\displaystyle U{}_{n}^{2}}$ can only be represented over fields with ${\displaystyle n-1}$ or more elements. However, every gammoid may be represented over almost every finite field.^[3][4] More specifically, a gammoid with element set ${\displaystyle S}$ may be represented over every field that has at least ${\displaystyle 2^{|S|}}$ elements.^[4][11][12]