Category Archives: Gammoids

A Quick and a Fun Introduction to Gammoids

Jersey Telecom switchboard and operator, Joseph A. Carr, 1975. (https://commons.wikimedia.org/wiki/File:Jersey_Telecom_switchboard_and_operator.jpg)

Summary

In this post, we give a short stand-alone definition of the class of gammoids requiring only knowledge of basic set theory. If you do not like to read the maths, skip right to the fun part in English at the end.

Matroids

Gammoids are special matroids, therefore, we have to define this notion first. Note that there are many cryptomorphic ways to define what is essentially the same structure, our definition here is more precisely called an independence matroid.

Definition

Let $E$ be a finite set, and let $\Ical \subseteq 2^E$ be a family of subsets of $E$. Here, we call $E$ the ground set, elements $e\in E$ are called edges, and members of $X\in\Ical$ are called independent. The pair $M=(E,\Ical)$ is called a matroid, if the following three properties are satisfied:

  1. $\emptyset \in \Ical$ — the empty set is independent.
  2. $\forall X \in \Ical\colon 2^X \subseteq \Ical$ — each subset of an independent set is independent.
  3. $\forall X,Y\in \Ical\colon \CARD{Y} > \CARD{X} \Rightarrow \exists y\in Y\BS X\colon X\cup\SET{y} \in \Ical$ — given two independent sets $X$ and $Y$, if $Y$ is bigger than $X$, then there is an element $y\in Y$ that is not a member of $X$, and which may be used to augment $X$ to $X\cup\SET{y}$ such that the augmented set is again independent.

Consider $M\in \Rbb^{n\times m}$ — an $m\times n$-matrix in the reals. If we set $E=\SET{1,2,\ldots,n}$ and let $\Ical$ be the family of subsets $X$ of $E$ such that there is no non-trivial linear combination of the zero vector using only the rows of $M$ that correspond to $X$. Then $M=(E,\Ical)$ is an example of a matroid.

Digraphs

If you want to talk about gammoids, you also have to talk about digraphs a.k.a. directed graphs.

Definition

A digraph is a pair $D=(V,A)$ where $V$ is a finite set and $A\subseteq V\times V$. Each element $v\in V$ is called a vertex of $D$ and each $a=(u,v)\in A$ is called an arc of $D$. The vertex $u$ is the tail of the arc $a$ and the vertex $v$ is the head of the arc $a$.

A word of caution: if you are like me, then you will constantly confuse the head and the tail of an arc, because in a list $(a,b,c,d,e)$, you would call $a$ the head and $(b,c,d,e)$ the tail. But with arcs $(\rightarrow)$, the tails come first, then do the heads! So beware that this mistake might come up here sooner or later, too.

A path in $D$ is a non-empty, non-repeating sequence of vertices $p=(v_1, v_2, \ldots, v_n)$ (where $0<n\in \Nbb$ and $v_i = v_j \Rightarrow i=j$) such that for each $0<i<n$ there is an arc $(v_i,v_{i+1})\in A$. The set of traversed vertices of $p$ is $\CARD{p} = \SET{v_1, v_2, \ldots, v_n}$. The source of $p$ is its first vertex $p_1 = v_1$ and the target of $p$ is its last vertex $p_{-1} = v_n$. The set of all paths in $D$ is denoted by $\Pbb(D)$.

There are two common relaxations of this notion that we won’t use here: a trail allows that vertices to repeat, but the arcs $(v_i,v_{i+1})$ may not repeat; whereas a walk just requires that two consecutive vertices are connected by an arc, but both vertices and arcs may be traversed repeatedly.

Routings

Routings are an important notion used in the definition of gammoids, thus they get their own section, albeit this is just another digraph related definition.

Definition

Let $D=(V,A)$ be a digraph, and let $R\subseteq \Pbb(D)$ be a family of paths in $D$. Then $R$ is a routing if the following implication holds for all $p,q\in R$: $$ \CARD{p}\cap \CARD{q}\not=\emptyset \Rightarrow p=q. $$

So a routing is nothing more than just a bunch of paths in a digraph that do not touch each other. We are most interested in the sources and targets of routings in $D$. We write $R\colon X\routesto Y$ to denote a routing $R$ where $X=\SET{p_1 \mid p\in R}$ and $Y\supseteq\SET{p_{-1} \mid p\in R}$ and we say that $R$ is a routing from $X$ to $Y$ in $D$. If $Y=\SET{p_{-1} \mid p\in R}$, we say that $R$ is a linking from $X$ onto $Y$ in $D$.

Gammoids

Now we have collected all the necessary notions we need in order to define gammoids.

Definition

Let $D=(V,A)$ be a digraph, $E\subseteq V$, and $T\subseteq V$. We define the gammoid represented by $(D,T,E)$ to be the matroid $\Gamma(D,T,E) = (E,\Ical)$ such that for all $X\subseteq E$ we have $X\in\Ical$ if and only if there is a routing $R_X\colon X\routesto T$ in $D$. The elements $t\in T$ are called targets of the representation $(D,T,E)$.

A matroid $M=(E,\Ical)$ is a gammoid, if $M=\Gamma(D,T,E)$ for some digraph $D=(V,A)$ with $E\subseteq V$ and some set of targets $T\subseteq V$. Furthermore, $M$ is a strict gammoid, if $M=\Gamma(D,T,E)$ for a digraph $D=(V,A)$ with $V=E$ and some set of targets $T\subseteq E$.

Gammoids Work A Bit Like Switchboards

First, a little disclaimer: I do not really know how telephone operator switchboards work (or used to), and I am quite sure that there is more to it than just what I describe here.

Anyway, this is your first day at the Awesome Switchboard Operations Corp., and you are the new operator! Your cubicle has a switchboard in it, which consists of a bunch of banana-plug chords (which have numbers attached to them) and has a bunch of banana-sockets on display (also with numbers on them). You can also see some light bulbs (they have numbers attached to them, too — you sense that this a rather meticulous workplace).

Some of the plugs have numbers on them that you also see on one of the sockets. Your supervisor tells you, that plugs and sockets with the same number are internally connected by a wire. The plugs that have numbers that do not appear on the sockets array are connected to the (+)-pole of a single battery. The sockets with numbers that do not appear on any plug are connected to a light bulb with the same number, which in turn is connected to the (-)-pole of the same battery.

Your job is the following: given a list of numbers of light bulbs, you must connect the plugs to the sockets such that the maximal possible number of these bulbs light up. ‘Easy’, you may think, you just might want to connect the battery-plugs to the lamp-sockets on the list until either the list is all worked up or there are no more battery-plugs available. As you turn your head, you see that your supervisor has a big book for you to read. It’s called the Awesome Switchboard Operations Corp. Operator Rule Book. You take a look inside:

1st Rule: You may not connect any plug to any socket unless it has been explicitly allowed by another rule.

2nd Rule: You may plug the plug with number 8 into the socket with number 4.

3rd Rule: You may plug the plug with number 3 into the socket with number 4.

4th Rule: You may plug the plug with number 8 into the socket with number 5.

[…]

Your supervisor tells you, that back in the old days, the rule book only contained pairs of numbers, like $(4,8), (4,3), (5,8), \ldots$. But this was considered too confusing by the company lawyers and thus replaced by the above rule book in prose English. Back then, one of the biggest problems was that $(4,8)$ in the book would allow you to plug the number $8$ into the number $4$. But it was too often misinterpreted as allowing to plug the number $4$ into the socket with the $8$. You are warned to take the rules seriously, as failure to obey these rules will trigger immediate termination without notice. Apart from these harsh personal consequences, there is a rumor that it is possible that an illegal patching will cause the plasma-coils in the basement to overload and that in turn leads to a core melt-down.

Anyway, the supervisor wishes you all the best and leaves not before mentioning that most of the expert operators collect all the battery-plug numbers on a list they call the $T$-list, the lamp-socket numbers on a list they call the $E$-list, and that they use the old rule book, which they call $A$-list — the supervisor also recalls them muttering something about independent lights and possibly something about gamma-rays. — If only you had read carefully from the beginning.